[mirror_qemu.git] / util / 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 "qemu/osdep.h"
#include "qemu/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 >= 4*BITS_PER_LONG) {
        unsigned long d1, d2, d3;
        tmp = *p;
        d1 = *(p+1);
        d2 = *(p+2);
        d3 = *(p+3);
        if (tmp) {
            goto found_middle;
        }
        if (d1 | d2 | d3) {
            break;
        }
        p += 4;
        result += 4*BITS_PER_LONG;
        size -= 4*BITS_PER_LONG;
    }
    while (size >= BITS_PER_LONG) {
        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 + ctzl(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 + ctzl(~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 + BITS_PER_LONG - 1 - clzl(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
aafd7584	14	#include "qemu/osdep.h"
1de7afc9	15	#include "qemu/bitops.h"
e0e53b2f CC	16
	17	#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
	18
	19	/*
	20	* Find the next set bit in a memory region.
	21	*/
	22	unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
	23	unsigned long offset)
	24	{
	25	const unsigned long *p = addr + BITOP_WORD(offset);
	26	unsigned long result = offset & ~(BITS_PER_LONG-1);
	27	unsigned long tmp;
	28
	29	if (offset >= size) {
	30	return size;
	31	}
	32	size -= result;
	33	offset %= BITS_PER_LONG;
	34	if (offset) {
	35	tmp = *(p++);
	36	tmp &= (~0UL << offset);
	37	if (size < BITS_PER_LONG) {
	38	goto found_first;
	39	}
	40	if (tmp) {
	41	goto found_middle;
	42	}
	43	size -= BITS_PER_LONG;
	44	result += BITS_PER_LONG;
	45	}
49f676a0 PL	46	while (size >= 4*BITS_PER_LONG) {
	47	unsigned long d1, d2, d3;
	48	tmp = *p;
	49	d1 = *(p+1);
	50	d2 = *(p+2);
	51	d3 = *(p+3);
	52	if (tmp) {
	53	goto found_middle;
	54	}
	55	if (d1 \| d2 \| d3) {
	56	break;
	57	}
	58	p += 4;
	59	result += 4*BITS_PER_LONG;
	60	size -= 4*BITS_PER_LONG;
	61	}
	62	while (size >= BITS_PER_LONG) {
e0e53b2f CC	63	if ((tmp = *(p++))) {
	64	goto found_middle;
	65	}
	66	result += BITS_PER_LONG;
	67	size -= BITS_PER_LONG;
	68	}
	69	if (!size) {
	70	return result;
	71	}
	72	tmp = *p;
	73
	74	found_first:
	75	tmp &= (~0UL >> (BITS_PER_LONG - size));
	76	if (tmp == 0UL) { /* Are any bits set? */
	77	return result + size; /* Nope. */
	78	}
	79	found_middle:
265ce4a5	80	return result + ctzl(tmp);
e0e53b2f CC	81	}
	82
	83	/*
	84	* This implementation of find_{first,next}_zero_bit was stolen from
	85	* Linus' asm-alpha/bitops.h.
	86	*/
	87	unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
	88	unsigned long offset)
	89	{
	90	const unsigned long *p = addr + BITOP_WORD(offset);
	91	unsigned long result = offset & ~(BITS_PER_LONG-1);
	92	unsigned long tmp;
	93
	94	if (offset >= size) {
	95	return size;
	96	}
	97	size -= result;
	98	offset %= BITS_PER_LONG;
	99	if (offset) {
	100	tmp = *(p++);
	101	tmp \|= ~0UL >> (BITS_PER_LONG - offset);
	102	if (size < BITS_PER_LONG) {
	103	goto found_first;
	104	}
	105	if (~tmp) {
	106	goto found_middle;
	107	}
	108	size -= BITS_PER_LONG;
	109	result += BITS_PER_LONG;
	110	}
	111	while (size & ~(BITS_PER_LONG-1)) {
	112	if (~(tmp = *(p++))) {
	113	goto found_middle;
	114	}
	115	result += BITS_PER_LONG;
	116	size -= BITS_PER_LONG;
	117	}
	118	if (!size) {
	119	return result;
	120	}
	121	tmp = *p;
	122
	123	found_first:
	124	tmp \|= ~0UL << size;
	125	if (tmp == ~0UL) { /* Are any bits zero? */
	126	return result + size; /* Nope. */
	127	}
	128	found_middle:
0f9d8bd3	129	return result + ctzl(~tmp);
e0e53b2f CC	130	}
	131
	132	unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
	133	{
	134	unsigned long words;
	135	unsigned long tmp;
	136
	137	/* Start at final word. */
	138	words = size / BITS_PER_LONG;
	139
	140	/* Partial final word? */
	141	if (size & (BITS_PER_LONG-1)) {
	142	tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
	143	- (size & (BITS_PER_LONG-1)))));
	144	if (tmp) {
	145	goto found;
	146	}
	147	}
	148
	149	while (words) {
	150	tmp = addr[--words];
	151	if (tmp) {
	152	found:
4932398f	153	return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
e0e53b2f CC	154	}
	155	}
	156
	157	/* Not found */
	158	return size;
	159	}