bitmap with bit instructions

/*
 * Copyright (c) 2014 The Native Client Authors. All rights reserved.
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef BITMAP_H_
#define BITMAP_H_

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

#if defined(_MSC_VER)
# define BITMAP_INLINE __forceinline
#elif defined(__GNUC__)
# define BITMAP_INLINE __inline __attribute__ ((always_inline))
#else
# define BITMAP_INLINE inline
#endif

#if defined(__LP64__) || defined(_WIN64)
typedef uint64_t bitmap_word;
#else
typedef uint64_t bitmap_word;
#endif

static BITMAP_INLINE bitmap_word *bitmap_allocate(size_t indexes) {
  size_t word_count = ((indexes + sizeof(bitmap_word) - 1) / sizeof(bitmap_word));
  return (bitmap_word*)calloc(word_count, sizeof(bitmap_word));
}

#if (defined(__GNUC__) && (defined(__x86_64__) || defined(__i386__)) && \
    !defined(__native_client__))

/*
 * Unfortunately limitations of GNU inline assembler make it impossible for us
 * to create a single "perfect" function.  Thus we have two functions here.
 * Use bitmap_bit_is_set in "if (bitmap_bit_is_set(...))" constructs.
 * Use bitmap_is_bit_set in "a |= bitmap_is_bit_set(...)" constructs.
 */
static BITMAP_INLINE bool bitmap_bit_is_set(bitmap_word bitmap[],
                                            size_t index) {
  bool flag;
  asm goto ("bt {%[index],%[bitmap]|%[bitmap],%[index]}\n"
            "jc %l2"
            :
            : [bitmap]"m" (*bitmap),
              [index]"r"(index)
            : "cc"
            : bit_is_set);
  return 0;
bit_is_set:
  return 1;
}

static BITMAP_INLINE bool bitmap_is_bit_set(bitmap_word bitmap[],
                                            size_t index) {
  bool flag;
  asm("bt {%[index],%[bitmap]|%[bitmap],%[index]}\n"
      "setb %[flag]"
      : [flag]"=q"(flag)
      : [bitmap]"m" (*bitmap),
        [index]"r"(index)
      : "cc");
  return flag;
}

static BITMAP_INLINE void bitmap_set_bit(bitmap_word bitmap[], size_t index) {
  asm("bts {%[index],%[bitmap]|%[bitmap],%[index]}"
      : [bitmap]"+m" (*bitmap)
      : [index]"r"(index));
}

static BITMAP_INLINE void bitmap_clear_bit(bitmap_word bitmap[], size_t index) {
  asm("btc {%[index],%[bitmap]|%[bitmap],%[index]}"
      : [bitmap]"+m" (*bitmap)
      : [index]"r"(index));
}

#else

static BITMAP_INLINE bool bitmap_bit_is_set(bitmap_word bitmap[],
                                            size_t index) {
  return (bitmap[index / sizeof *bitmap] &
      (((bitmap_word)1) << (index % sizeof *bitmap))) != 0;
}

static BITMAP_INLINE bool bitmap_is_bit_set(bitmap_word bitmap[],
                                            size_t index) {
  return (bitmap[index / sizeof *bitmap] &
      (((bitmap_word)1) << (index % sizeof *bitmap))) != 0;
}

static BITMAP_INLINE void bitmap_set_bit(bitmap_word bitmap[], size_t index) {
  bitmap[index / sizeof *bitmap] |=
      ((bitmap_word)1) << (index % sizeof *bitmap);
}

static BITMAP_INLINE void bitmap_clear_bit(bitmap_word *bitmap, size_t index) {
  bitmap[index / sizeof *bitmap] &=
      ~(((bitmap_word)1) << (index % sizeof *bitmap));
}

#endif

#endif  /* BITMAP_H */