cachepc-qemu

Fork of AMDESE/qemu with changes for cachepc side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-qemu
Log | Files | Refs | Submodules | LICENSE | sfeed.txt

bitops.c (3921B)

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