Annotation of qemu/bitops.c, revision 1.1.1.1

1.1       root        1: /*
                      2:  * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
                      3:  * Written by David Howells (dhowells@redhat.com)
                      4:  * Copyright (C) 2008 IBM Corporation
                      5:  * Written by Rusty Russell <rusty@rustcorp.com.au>
                      6:  * (Inspired by David Howell's find_next_bit implementation)
                      7:  *
                      8:  * This program is free software; you can redistribute it and/or
                      9:  * modify it under the terms of the GNU General Public License
                     10:  * as published by the Free Software Foundation; either version
                     11:  * 2 of the License, or (at your option) any later version.
                     12:  */
                     13: 
                     14: #include "bitops.h"
                     15: 
                     16: #define BITOP_WORD(nr)         ((nr) / BITS_PER_LONG)
                     17: 
                     18: /*
                     19:  * Find the next set bit in a memory region.
                     20:  */
                     21: unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
                     22:                            unsigned long offset)
                     23: {
                     24:     const unsigned long *p = addr + BITOP_WORD(offset);
                     25:     unsigned long result = offset & ~(BITS_PER_LONG-1);
                     26:     unsigned long tmp;
                     27: 
                     28:     if (offset >= size) {
                     29:         return size;
                     30:     }
                     31:     size -= result;
                     32:     offset %= BITS_PER_LONG;
                     33:     if (offset) {
                     34:         tmp = *(p++);
                     35:         tmp &= (~0UL << offset);
                     36:         if (size < BITS_PER_LONG) {
                     37:             goto found_first;
                     38:         }
                     39:         if (tmp) {
                     40:             goto found_middle;
                     41:         }
                     42:         size -= BITS_PER_LONG;
                     43:         result += BITS_PER_LONG;
                     44:     }
                     45:     while (size & ~(BITS_PER_LONG-1)) {
                     46:         if ((tmp = *(p++))) {
                     47:             goto found_middle;
                     48:         }
                     49:         result += BITS_PER_LONG;
                     50:         size -= BITS_PER_LONG;
                     51:     }
                     52:     if (!size) {
                     53:         return result;
                     54:     }
                     55:     tmp = *p;
                     56: 
                     57: found_first:
                     58:     tmp &= (~0UL >> (BITS_PER_LONG - size));
                     59:     if (tmp == 0UL) {          /* Are any bits set? */
                     60:         return result + size;  /* Nope. */
                     61:     }
                     62: found_middle:
                     63:     return result + bitops_ffsl(tmp);
                     64: }
                     65: 
                     66: /*
                     67:  * This implementation of find_{first,next}_zero_bit was stolen from
                     68:  * Linus' asm-alpha/bitops.h.
                     69:  */
                     70: unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
                     71:                                 unsigned long offset)
                     72: {
                     73:     const unsigned long *p = addr + BITOP_WORD(offset);
                     74:     unsigned long result = offset & ~(BITS_PER_LONG-1);
                     75:     unsigned long tmp;
                     76: 
                     77:     if (offset >= size) {
                     78:         return size;
                     79:     }
                     80:     size -= result;
                     81:     offset %= BITS_PER_LONG;
                     82:     if (offset) {
                     83:         tmp = *(p++);
                     84:         tmp |= ~0UL >> (BITS_PER_LONG - offset);
                     85:         if (size < BITS_PER_LONG) {
                     86:             goto found_first;
                     87:         }
                     88:         if (~tmp) {
                     89:             goto found_middle;
                     90:         }
                     91:         size -= BITS_PER_LONG;
                     92:         result += BITS_PER_LONG;
                     93:     }
                     94:     while (size & ~(BITS_PER_LONG-1)) {
                     95:         if (~(tmp = *(p++))) {
                     96:             goto found_middle;
                     97:         }
                     98:         result += BITS_PER_LONG;
                     99:         size -= BITS_PER_LONG;
                    100:     }
                    101:     if (!size) {
                    102:         return result;
                    103:     }
                    104:     tmp = *p;
                    105: 
                    106: found_first:
                    107:     tmp |= ~0UL << size;
                    108:     if (tmp == ~0UL) { /* Are any bits zero? */
                    109:         return result + size;  /* Nope. */
                    110:     }
                    111: found_middle:
                    112:     return result + ffz(tmp);
                    113: }
                    114: 
                    115: unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
                    116: {
                    117:     unsigned long words;
                    118:     unsigned long tmp;
                    119: 
                    120:     /* Start at final word. */
                    121:     words = size / BITS_PER_LONG;
                    122: 
                    123:     /* Partial final word? */
                    124:     if (size & (BITS_PER_LONG-1)) {
                    125:         tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
                    126:                                        - (size & (BITS_PER_LONG-1)))));
                    127:         if (tmp) {
                    128:             goto found;
                    129:         }
                    130:     }
                    131: 
                    132:     while (words) {
                    133:         tmp = addr[--words];
                    134:         if (tmp) {
                    135:         found:
                    136:             return words * BITS_PER_LONG + bitops_flsl(tmp);
                    137:         }
                    138:     }
                    139: 
                    140:     /* Not found */
                    141:     return size;
                    142: }

unix.superglobalmegacorp.com