186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner/* 286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * Written by David Howells (dhowells@redhat.com) 486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * Copyright (C) 2008 IBM Corporation 586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * Written by Rusty Russell <rusty@rustcorp.com.au> 686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * (Inspired by David Howell's find_next_bit implementation) 786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * 886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * This program is free software; you can redistribute it and/or 986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * modify it under the terms of the GNU General Public License 1086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * as published by the Free Software Foundation; either version 1186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * 2 of the License, or (at your option) any later version. 1286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner */ 1386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 1486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner#include "qemu/bitops.h" 1586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 1686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) 1786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 1886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner/* 1986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * Find the next set bit in a memory region. 2086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner */ 2186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerunsigned long find_next_bit(const unsigned long *addr, unsigned long size, 2286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long offset) 2386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner{ 2486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner const unsigned long *p = addr + BITOP_WORD(offset); 2586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long result = offset & ~(BITS_PER_LONG-1); 2686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long tmp; 2786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 2886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (offset >= size) { 2986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return size; 3086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 3186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= result; 3286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner offset %= BITS_PER_LONG; 3386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (offset) { 3486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = *(p++); 3586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp &= (~0UL << offset); 3686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (size < BITS_PER_LONG) { 3786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_first; 3886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 3986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (tmp) { 4086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_middle; 4186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 4286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= BITS_PER_LONG; 4386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner result += BITS_PER_LONG; 4486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 4586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner while (size >= 4*BITS_PER_LONG) { 4686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long d1, d2, d3; 4786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = *p; 4886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner d1 = *(p+1); 4986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner d2 = *(p+2); 5086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner d3 = *(p+3); 5186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (tmp) { 5286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_middle; 5386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 5486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (d1 | d2 | d3) { 5586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner break; 5686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 5786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner p += 4; 5886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner result += 4*BITS_PER_LONG; 5986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= 4*BITS_PER_LONG; 6086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 6186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner while (size >= BITS_PER_LONG) { 6286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if ((tmp = *(p++))) { 6386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_middle; 6486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 6586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner result += BITS_PER_LONG; 6686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= BITS_PER_LONG; 6786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 6886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (!size) { 6986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return result; 7086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 7186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = *p; 7286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 7386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerfound_first: 7486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp &= (~0UL >> (BITS_PER_LONG - size)); 7586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (tmp == 0UL) { /* Are any bits set? */ 7686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return result + size; /* Nope. */ 7786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 7886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerfound_middle: 7986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return result + ctzl(tmp); 8086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner} 8186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 8286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner/* 8386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * This implementation of find_{first,next}_zero_bit was stolen from 8486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner * Linus' asm-alpha/bitops.h. 8586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner */ 8686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerunsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 8786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long offset) 8886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner{ 8986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner const unsigned long *p = addr + BITOP_WORD(offset); 9086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long result = offset & ~(BITS_PER_LONG-1); 9186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long tmp; 9286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 9386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (offset >= size) { 9486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return size; 9586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 9686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= result; 9786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner offset %= BITS_PER_LONG; 9886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (offset) { 9986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = *(p++); 10086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp |= ~0UL >> (BITS_PER_LONG - offset); 10186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (size < BITS_PER_LONG) { 10286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_first; 10386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 10486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (~tmp) { 10586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_middle; 10686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 10786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= BITS_PER_LONG; 10886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner result += BITS_PER_LONG; 10986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 11086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner while (size & ~(BITS_PER_LONG-1)) { 11186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (~(tmp = *(p++))) { 11286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found_middle; 11386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 11486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner result += BITS_PER_LONG; 11586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner size -= BITS_PER_LONG; 11686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 11786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (!size) { 11886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return result; 11986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 12086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = *p; 12186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 12286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerfound_first: 12386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp |= ~0UL << size; 12486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (tmp == ~0UL) { /* Are any bits zero? */ 12586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return result + size; /* Nope. */ 12686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 12786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerfound_middle: 12886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return result + ctzl(~tmp); 12986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner} 13086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 13186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turnerunsigned long find_last_bit(const unsigned long *addr, unsigned long size) 13286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner{ 13386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long words; 13486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner unsigned long tmp; 13586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 13686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner /* Start at final word. */ 13786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner words = size / BITS_PER_LONG; 13886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 13986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner /* Partial final word? */ 14086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (size & (BITS_PER_LONG-1)) { 14186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = (addr[words] & (~0UL >> (BITS_PER_LONG 14286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner - (size & (BITS_PER_LONG-1))))); 14386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (tmp) { 14486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner goto found; 14586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 14686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 14786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 14886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner while (words) { 14986b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner tmp = addr[--words]; 15086b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner if (tmp) { 15186b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner found: 15286b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp); 15386b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 15486b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner } 15586b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner 15686b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner /* Not found */ 15786b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner return size; 15886b1fb06ee6ef53d8961ce96343ba4aa37518840David 'Digit' Turner} 159