scsi: pvscsi: check command descriptor ring buffer size (CVE-2016-4952)
[qemu.git] / util / bitops.c
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 #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 }
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) {
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:
80 return result + ctzl(tmp);
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:
129 return result + ctzl(~tmp);
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:
153 return words * BITS_PER_LONG + BITS_PER_LONG - 1 - clzl(tmp);
154 }
155 }
156
157 /* Not found */
158 return size;
159 }