[qemu.git] / bitops.c

/*
 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 * Copyright (C) 2008 IBM Corporation
 * Written by Rusty Russell <rusty@rustcorp.com.au>
 * (Inspired by David Howell's find_next_bit implementation)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version
 * 2 of the License, or (at your option) any later version.
 */

#include "bitops.h"

#define BITOP_WORD(nr)		((nr) / BITS_PER_LONG)

/*
 * Find the next set bit in a memory region.
 */
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
			    unsigned long offset)
{
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;

    if (offset >= size) {
        return size;
    }
    size -= result;
    offset %= BITS_PER_LONG;
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);
        if (size < BITS_PER_LONG) {
            goto found_first;
        }
        if (tmp) {
            goto found_middle;
        }
        size -= BITS_PER_LONG;
        result += BITS_PER_LONG;
    }
    while (size & ~(BITS_PER_LONG-1)) {
        if ((tmp = *(p++))) {
            goto found_middle;
        }
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if (!size) {
        return result;
    }
    tmp = *p;

found_first:
    tmp &= (~0UL >> (BITS_PER_LONG - size));
    if (tmp == 0UL) {		/* Are any bits set? */
        return result + size;	/* Nope. */
    }
found_middle:
    return result + bitops_ffsl(tmp);
}

/*
 * This implementation of find_{first,next}_zero_bit was stolen from
 * Linus' asm-alpha/bitops.h.
 */
unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
				 unsigned long offset)
{
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;

    if (offset >= size) {
        return size;
    }
    size -= result;
    offset %= BITS_PER_LONG;
    if (offset) {
        tmp = *(p++);
        tmp |= ~0UL >> (BITS_PER_LONG - offset);
        if (size < BITS_PER_LONG) {
            goto found_first;
        }
        if (~tmp) {
            goto found_middle;
        }
        size -= BITS_PER_LONG;
        result += BITS_PER_LONG;
    }
    while (size & ~(BITS_PER_LONG-1)) {
        if (~(tmp = *(p++))) {
            goto found_middle;
        }
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if (!size) {
        return result;
    }
    tmp = *p;

found_first:
    tmp |= ~0UL << size;
    if (tmp == ~0UL) {	/* Are any bits zero? */
        return result + size;	/* Nope. */
    }
found_middle:
    return result + ffz(tmp);
}

unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
    unsigned long words;
    unsigned long tmp;

    /* Start at final word. */
    words = size / BITS_PER_LONG;

    /* Partial final word? */
    if (size & (BITS_PER_LONG-1)) {
        tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
                                       - (size & (BITS_PER_LONG-1)))));
        if (tmp) {
            goto found;
        }
    }

    while (words) {
        tmp = addr[--words];
        if (tmp) {
        found:
            return words * BITS_PER_LONG + bitops_flsl(tmp);
        }
    }

    /* Not found */
    return size;
}
Commit	Line	Data
e0e53b2f CC	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	}