1 /*
2 Copyright (c) 2007, 2021, Oracle and/or its affiliates.
3 All rights reserved. Use is subject to license terms.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24 */
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <stdint.h>
30 #include <assert.h>
31
32 #define N (1024*1024)
33 #define S 65537
34 /* The number S must be relative prime to N. */
35
36 uint32_t bm[N*4];
37
38 uint32_t bms[N][4];
39 uint32_t len[N];
40 uint32_t pos[N];
41
42 typedef uint32_t Uint32;
43 #define MEMCOPY_NO_WORDS(to, from, no_of_words) \
44 memcpy((to), (void*)(from), (size_t)(no_of_words << 2));
45
46 /****************************************************************************/
47 static void
getbits(const Uint32 * src,Uint32 bit_pos,Uint32 * dst,Uint32 count)48 getbits(const Uint32 *src, Uint32 bit_pos, Uint32 *dst, Uint32 count)
49 {
50 Uint32 val;
51
52 /* Move to start word in src. */
53 src+= bit_pos>>5;
54 bit_pos&= 31;
55
56 /*
57 If word-aligned, copy word-for-word is faster and avoids edge
58 cases with undefined bitshift operations.
59 */
60 if (bit_pos==0)
61 {
62 MEMCOPY_NO_WORDS(dst, src, count>>5);
63 src+= count>>5;
64 dst+= count>>5;
65 count&= 31;
66 }
67 else
68 {
69 while(count >= 32)
70 {
71 /*
72 Get bits 0-X from first source word.
73 Get bits (X+1)-31 from second source word.
74 Handle endian so that we store bit 0 in the first byte, and bit 31 in
75 the last byte, so that we don't waste space on 32-bit aligning the
76 bitmap.
77 */
78 #ifdef WORDS_BIGENDIAN
79 Uint32 firstpart_len= 32-bit_pos;
80 val= *src++ & (((Uint32)1<<firstpart_len)-1);
81 val|= *src & ((Uint32)0xffffffff << firstpart_len);
82 #else
83 val= *src++ >> bit_pos;
84 val|= *src << (32-bit_pos);
85 #endif
86 *dst++= val;
87 count-= 32;
88 }
89 }
90
91 /* Handle any partial word at the end. */
92 if (count>0)
93 {
94 if (bit_pos+count <= 32)
95 {
96 /* Last part is wholly contained in one source word. */
97 #ifdef WORDS_BIGENDIAN
98 val= *src >> (32-(bit_pos+count));
99 #else
100 val= *src >> bit_pos;
101 #endif
102 }
103 else
104 {
105 /* Need to assemble last part from two source words. */
106 #ifdef WORDS_BIGENDIAN
107 Uint32 firstpart_len= 32-bit_pos;
108 val= *src++ & (((Uint32)1<<firstpart_len)-1);
109 val|= (*src >> (32-count)) & ((Uint32)0xffffffff << firstpart_len);
110 #else
111 val= *src++ >> bit_pos;
112 val|= *src << (32-bit_pos);
113 #endif
114 }
115 /* Mask off any unused bits. */
116 *dst= val & (((Uint32)1<<count)-1);
117 }
118 }
119
120 static void
setbits(const Uint32 * src,Uint32 * dst,Uint32 bit_pos,Uint32 count)121 setbits(const Uint32 *src, Uint32 *dst, Uint32 bit_pos, Uint32 count)
122 {
123 Uint32 val;
124
125 /* Move to start word in dst. */
126
127 dst+= bit_pos>>5;
128 bit_pos&= 31;
129
130 #ifdef WORDS_BIGENDIAN
131 Uint32 low_mask= ((Uint32)0xffffffff)<<(32-bit_pos);
132 Uint32 high_mask= ~low_mask;
133 #else
134 Uint32 low_mask= (((Uint32)1)<<bit_pos) - 1;
135 Uint32 high_mask= ~low_mask;
136 #endif
137
138 if (bit_pos==0)
139 {
140 MEMCOPY_NO_WORDS(dst, src, count>>5);
141 src+= count>>5;
142 dst+= count>>5;
143 count&= 31;
144 }
145 else
146 {
147 while (count >= 32)
148 {
149 val= *src++;
150 #ifdef WORDS_BIGENDIAN
151 *dst= (*dst&low_mask) | (val&high_mask);
152 dst++;
153 *dst= (*dst&high_mask) | (val&low_mask);
154 #else
155 *dst= (*dst&low_mask) | (val<<bit_pos);
156 dst++;
157 *dst= (*dst&high_mask) | (val>>(32-bit_pos));
158 #endif
159 count-= 32;
160 }
161 }
162
163 /* Handle any partial word at the end. */
164 if (count > 0)
165 {
166 val= *src;
167 if (bit_pos+count <= 32)
168 {
169 /* Remaining part fits in one word of destination. */
170 Uint32 end_mask= (((Uint32)1)<<count) - 1;
171 #ifdef WORDS_BIGENDIAN
172 Uint32 shift= (32-(bit_pos+count));
173 *dst= (*dst&~(end_mask<<shift)) | ((val&end_mask)<<shift);
174 #else
175 *dst= (*dst&~(end_mask<<bit_pos)) | ((val&end_mask)<<bit_pos);
176 #endif
177 }
178 else
179 {
180 /* Need to split the remaining part across two destination words. */
181 #ifdef WORDS_BIGENDIAN
182 *dst= (*dst&low_mask) | (val&high_mask);
183 dst++;
184 Uint32 shift= 32-count;
185 Uint32 end_mask= ((((Uint32)1)<<(bit_pos+count-32)) - 1) << (32-bit_pos);
186 *dst= (*dst&~(end_mask<<shift)) | ((val&end_mask)<<shift);
187 #else
188 *dst= (*dst&low_mask) | (val<<bit_pos);
189 dst++;
190 Uint32 end_mask= (((Uint32)1)<<(count+bit_pos-32)) - 1;
191 *dst= (*dst&~end_mask) | ((val>>(32-bit_pos))&end_mask);
192 #endif
193 }
194 }
195 }
196 /****************************************************************************/
197
198 /* Set up a bunch of test bit fields. */
fill(void)199 void fill(void)
200 {
201 uint32_t i,j;
202 uint32_t p= 0;
203
204 for(i= 0; i<N; i++)
205 {
206 memset(bms[i], 0, sizeof(bms[i]));
207 pos[i]= p;
208 do
209 len[i]= rand()%128;
210 while (!len[i]);
211 p+= len[i];
212 for(j= 0; j<len[i]; j++)
213 if(rand()%2)
214 bms[i][j>>5]|= (((uint32_t)1)<<(j&31));
215 }
216 }
217
write(void)218 void write(void)
219 {
220 uint32_t i, idx;
221
222 for(i=0, idx=0; i<N; i++, idx+= S)
223 {
224 if(idx>=N)
225 idx-= N;
226 setbits(&(bms[idx][0]), &(bm[0]), pos[idx], len[idx]);
227 }
228 }
229
read(void)230 void read(void)
231 {
232 uint32_t buf[4];
233 uint32_t i;
234
235 for(i=0; i<N; i++)
236 {
237 getbits(&(bm[0]), pos[i], &(buf[0]), len[i]);
238 assert(0==memcmp(buf, bms[i], ((len[i]+31)>>5)<<2));
239 }
240 }
241
main(int argc,char * argv[])242 int main(int argc, char *argv[])
243 {
244 uint32_t i;
245
246 srand(1);
247 fill();
248 write();
249 read();
250
251 exit(0);
252 return 0;
253 }
254