Annotation of qemu/bitops.c, revision 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