File:  [Qemu by Fabrice Bellard] / qemu / bitmap.c
Revision 1.1.1.1 (vendor branch): download - view: text, annotated - select for diffs
Tue Apr 24 18:56:29 2018 UTC (3 years, 1 month ago) by root
Branches: qemu, MAIN
CVS tags: qemu1101, qemu1001, qemu1000, qemu0151, HEAD
qemu 0.15.1

    1: /*
    2:  * Bitmap Module
    3:  *
    4:  * Stolen from linux/src/lib/bitmap.c
    5:  *
    6:  * Copyright (C) 2010 Corentin Chary
    7:  *
    8:  * This source code is licensed under the GNU General Public License,
    9:  * Version 2.
   10:  */
   11: 
   12: #include "bitops.h"
   13: #include "bitmap.h"
   14: 
   15: /*
   16:  * bitmaps provide an array of bits, implemented using an an
   17:  * array of unsigned longs.  The number of valid bits in a
   18:  * given bitmap does _not_ need to be an exact multiple of
   19:  * BITS_PER_LONG.
   20:  *
   21:  * The possible unused bits in the last, partially used word
   22:  * of a bitmap are 'don't care'.  The implementation makes
   23:  * no particular effort to keep them zero.  It ensures that
   24:  * their value will not affect the results of any operation.
   25:  * The bitmap operations that return Boolean (bitmap_empty,
   26:  * for example) or scalar (bitmap_weight, for example) results
   27:  * carefully filter out these unused bits from impacting their
   28:  * results.
   29:  *
   30:  * These operations actually hold to a slightly stronger rule:
   31:  * if you don't input any bitmaps to these ops that have some
   32:  * unused bits set, then they won't output any set unused bits
   33:  * in output bitmaps.
   34:  *
   35:  * The byte ordering of bitmaps is more natural on little
   36:  * endian architectures.
   37:  */
   38: 
   39: int slow_bitmap_empty(const unsigned long *bitmap, int bits)
   40: {
   41:     int k, lim = bits/BITS_PER_LONG;
   42: 
   43:     for (k = 0; k < lim; ++k) {
   44:         if (bitmap[k]) {
   45:             return 0;
   46:         }
   47:     }
   48:     if (bits % BITS_PER_LONG) {
   49:         if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
   50:             return 0;
   51:         }
   52:     }
   53: 
   54:     return 1;
   55: }
   56: 
   57: int slow_bitmap_full(const unsigned long *bitmap, int bits)
   58: {
   59:     int k, lim = bits/BITS_PER_LONG;
   60: 
   61:     for (k = 0; k < lim; ++k) {
   62:         if (~bitmap[k]) {
   63:             return 0;
   64:         }
   65:     }
   66: 
   67:     if (bits % BITS_PER_LONG) {
   68:         if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
   69:             return 0;
   70:         }
   71:     }
   72: 
   73:     return 1;
   74: }
   75: 
   76: int slow_bitmap_equal(const unsigned long *bitmap1,
   77:                       const unsigned long *bitmap2, int bits)
   78: {
   79:     int k, lim = bits/BITS_PER_LONG;
   80: 
   81:     for (k = 0; k < lim; ++k) {
   82:         if (bitmap1[k] != bitmap2[k]) {
   83:             return 0;
   84:         }
   85:     }
   86: 
   87:     if (bits % BITS_PER_LONG) {
   88:         if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
   89:             return 0;
   90:         }
   91:     }
   92: 
   93:     return 1;
   94: }
   95: 
   96: void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
   97:                             int bits)
   98: {
   99:     int k, lim = bits/BITS_PER_LONG;
  100: 
  101:     for (k = 0; k < lim; ++k) {
  102:         dst[k] = ~src[k];
  103:     }
  104: 
  105:     if (bits % BITS_PER_LONG) {
  106:         dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
  107:     }
  108: }
  109: 
  110: int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  111:                     const unsigned long *bitmap2, int bits)
  112: {
  113:     int k;
  114:     int nr = BITS_TO_LONGS(bits);
  115:     unsigned long result = 0;
  116: 
  117:     for (k = 0; k < nr; k++) {
  118:         result |= (dst[k] = bitmap1[k] & bitmap2[k]);
  119:     }
  120:     return result != 0;
  121: }
  122: 
  123: void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  124:                     const unsigned long *bitmap2, int bits)
  125: {
  126:     int k;
  127:     int nr = BITS_TO_LONGS(bits);
  128: 
  129:     for (k = 0; k < nr; k++) {
  130:         dst[k] = bitmap1[k] | bitmap2[k];
  131:     }
  132: }
  133: 
  134: void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
  135:                      const unsigned long *bitmap2, int bits)
  136: {
  137:     int k;
  138:     int nr = BITS_TO_LONGS(bits);
  139: 
  140:     for (k = 0; k < nr; k++) {
  141:         dst[k] = bitmap1[k] ^ bitmap2[k];
  142:     }
  143: }
  144: 
  145: int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
  146:                        const unsigned long *bitmap2, int bits)
  147: {
  148:     int k;
  149:     int nr = BITS_TO_LONGS(bits);
  150:     unsigned long result = 0;
  151: 
  152:     for (k = 0; k < nr; k++) {
  153:         result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
  154:     }
  155:     return result != 0;
  156: }
  157: 
  158: #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
  159: 
  160: void bitmap_set(unsigned long *map, int start, int nr)
  161: {
  162:     unsigned long *p = map + BIT_WORD(start);
  163:     const int size = start + nr;
  164:     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  165:     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
  166: 
  167:     while (nr - bits_to_set >= 0) {
  168:         *p |= mask_to_set;
  169:         nr -= bits_to_set;
  170:         bits_to_set = BITS_PER_LONG;
  171:         mask_to_set = ~0UL;
  172:         p++;
  173:     }
  174:     if (nr) {
  175:         mask_to_set &= BITMAP_LAST_WORD_MASK(size);
  176:         *p |= mask_to_set;
  177:     }
  178: }
  179: 
  180: void bitmap_clear(unsigned long *map, int start, int nr)
  181: {
  182:     unsigned long *p = map + BIT_WORD(start);
  183:     const int size = start + nr;
  184:     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
  185:     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
  186: 
  187:     while (nr - bits_to_clear >= 0) {
  188:         *p &= ~mask_to_clear;
  189:         nr -= bits_to_clear;
  190:         bits_to_clear = BITS_PER_LONG;
  191:         mask_to_clear = ~0UL;
  192:         p++;
  193:     }
  194:     if (nr) {
  195:         mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
  196:         *p &= ~mask_to_clear;
  197:     }
  198: }
  199: 
  200: #define ALIGN_MASK(x,mask)      (((x)+(mask))&~(mask))
  201: 
  202: /**
  203:  * bitmap_find_next_zero_area - find a contiguous aligned zero area
  204:  * @map: The address to base the search on
  205:  * @size: The bitmap size in bits
  206:  * @start: The bitnumber to start searching at
  207:  * @nr: The number of zeroed bits we're looking for
  208:  * @align_mask: Alignment mask for zero area
  209:  *
  210:  * The @align_mask should be one less than a power of 2; the effect is that
  211:  * the bit offset of all zero areas this function finds is multiples of that
  212:  * power of 2. A @align_mask of 0 means no alignment is required.
  213:  */
  214: unsigned long bitmap_find_next_zero_area(unsigned long *map,
  215: 					 unsigned long size,
  216: 					 unsigned long start,
  217: 					 unsigned int nr,
  218: 					 unsigned long align_mask)
  219: {
  220:     unsigned long index, end, i;
  221: again:
  222:     index = find_next_zero_bit(map, size, start);
  223: 
  224:     /* Align allocation */
  225:     index = ALIGN_MASK(index, align_mask);
  226: 
  227:     end = index + nr;
  228:     if (end > size) {
  229:         return end;
  230:     }
  231:     i = find_next_bit(map, end, index);
  232:     if (i < end) {
  233:         start = i + 1;
  234:         goto again;
  235:     }
  236:     return index;
  237: }
  238: 
  239: int slow_bitmap_intersects(const unsigned long *bitmap1,
  240:                            const unsigned long *bitmap2, int bits)
  241: {
  242:     int k, lim = bits/BITS_PER_LONG;
  243: 
  244:     for (k = 0; k < lim; ++k) {
  245:         if (bitmap1[k] & bitmap2[k]) {
  246:             return 1;
  247:         }
  248:     }
  249: 
  250:     if (bits % BITS_PER_LONG) {
  251:         if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
  252:             return 1;
  253:         }
  254:     }
  255:     return 0;
  256: }

unix.superglobalmegacorp.com