source: trunk/indexers/mg/lib/bitio_m.h@ 3745

Last change on this file since 3745 was 3745, checked in by mdewsnip, 21 years ago

Addition of MG package for search and retrieval
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 15.1 KB
Line 
1/**************************************************************************
2 *
3 * bitio_m.h -- Macros for bitio
4 * Copyright (C) 1994 Neil Sharman and Alistair Moffat
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 *
20 * $Id: bitio_m.h 3745 2003-02-20 21:20:24Z mdewsnip $
21 *
22 **************************************************************************/
23
24
25#ifndef H_BITIO_M
26#define H_BITIO_M
27
28/* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- */
29
30#ifndef BIO_ENCODE_PROLOGUE
31#define BIO_ENCODE_PROLOGUE
32#endif
33
34#ifndef BIO_DECODE_PROLOGUE
35#define BIO_DECODE_PROLOGUE
36#endif
37
38#ifndef BIO_ENCODE_EPILOGUE
39#define BIO_ENCODE_EPILOGUE
40#endif
41
42#ifndef BIO_DECODE_EPILOGUE
43#define BIO_DECODE_EPILOGUE
44#endif
45
46#ifndef DECODE_ADD
47#define DECODE_ADD(b) (b) += (b) + DECODE_BIT
48#endif
49
50/* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- */
51
52#define POSITIVE(f, x) \
53 if ((x)<=0) \
54 fprintf(stderr,"Error: Cannot "#f" encode %lu\n",(unsigned long)x),exit(1);
55
56
57#define CEILLOG_2(x,v) \
58do { \
59 register int _B_x = (x) - 1; \
60 (v) = 0; \
61 for (; _B_x ; _B_x>>=1, (v)++); \
62} while(0)
63
64
65#define FLOORLOG_2(x,v) \
66do { \
67 register int _B_x = (x); \
68 (v) = -1; \
69 for (; _B_x ; _B_x>>=1, (v)++); \
70} while(0)
71
72
73/****************************************************************************/
74
75
76
77#define UNARY_ENCODE(x) \
78do { \
79 register unsigned long _B_x = (x); \
80 BIO_ENCODE_PROLOGUE; \
81 POSITIVE(unary, _B_x); \
82 while(--_B_x) ENCODE_BIT(0); \
83 ENCODE_BIT(1); \
84 BIO_ENCODE_EPILOGUE; \
85} while(0)
86
87#define UNARY_ENCODE_L(x, count) \
88do { \
89 register unsigned long _B_x = (x); \
90 BIO_ENCODE_PROLOGUE; \
91 POSITIVE(unary, _B_x); \
92 (count) += _B_x; \
93 while(--_B_x) ENCODE_BIT(0); \
94 ENCODE_BIT(1); \
95 BIO_ENCODE_EPILOGUE; \
96} while(0)
97
98#define UNARY_DECODE(x) \
99do { \
100 BIO_DECODE_PROLOGUE; \
101 (x) = 1; \
102 while (!DECODE_BIT) (x)++; \
103 BIO_DECODE_EPILOGUE; \
104} while(0)
105
106#define UNARY_DECODE_L(x, count) \
107do { \
108 BIO_DECODE_PROLOGUE; \
109 (x) = 1; \
110 while (!DECODE_BIT) (x)++; \
111 (count) += (x); \
112 BIO_DECODE_EPILOGUE; \
113} while(0)
114
115
116#define UNARY_LENGTH(x, count) \
117do { \
118 POSITIVE(unary, x); \
119 (count) = (x); \
120} while(0)
121
122
123/****************************************************************************/
124
125
126#define BINARY_ENCODE(x, b) \
127do { \
128 register unsigned long _B_x = (x); \
129 register unsigned long _B_b = (b); \
130 register int _B_nbits, _B_logofb, _B_thresh; \
131 BIO_ENCODE_PROLOGUE; \
132 POSITIVE(binary, _B_x); \
133 CEILLOG_2(_B_b, _B_logofb); \
134 _B_thresh = (1<<_B_logofb) - _B_b; \
135 if (--_B_x < _B_thresh) \
136 _B_nbits = _B_logofb-1; \
137 else \
138 { \
139 _B_nbits = _B_logofb; \
140 _B_x += _B_thresh; \
141 } \
142 while (--_B_nbits>=0) \
143 ENCODE_BIT((_B_x>>_B_nbits) & 0x1); \
144 BIO_ENCODE_EPILOGUE; \
145} while(0)
146
147#define BINARY_ENCODE_L(x, b, count) \
148do { \
149 register unsigned long _B_x = (x); \
150 register unsigned long _B_b = (b); \
151 register int _B_nbits, _B_logofb, _B_thresh; \
152 BIO_ENCODE_PROLOGUE; \
153 POSITIVE(binary, _B_x); \
154 CEILLOG_2(_B_b, _B_logofb); \
155 _B_thresh = (1<<_B_logofb) - _B_b; \
156 if (--_B_x < _B_thresh) \
157 _B_nbits = _B_logofb-1; \
158 else \
159 { \
160 _B_nbits = _B_logofb; \
161 _B_x += _B_thresh; \
162 } \
163 (count) += _B_nbits; \
164 while (--_B_nbits>=0) \
165 ENCODE_BIT((_B_x>>_B_nbits) & 0x1); \
166 BIO_ENCODE_EPILOGUE; \
167} while(0)
168
169
170#define BINARY_DECODE(x, b) \
171do { \
172 register unsigned long _B_x = 0; \
173 register unsigned long _B_b = (b); \
174 register int _B_i, _B_logofb, _B_thresh; \
175 BIO_DECODE_PROLOGUE; \
176 if (_B_b != 1) \
177 { \
178 CEILLOG_2(_B_b, _B_logofb); \
179 _B_thresh = (1<<_B_logofb) - _B_b; \
180 _B_logofb--; \
181 for (_B_i=0; _B_i < _B_logofb; _B_i++) \
182 DECODE_ADD(_B_x); \
183 if (_B_x >= _B_thresh) \
184 { \
185 DECODE_ADD(_B_x); \
186 _B_x -= _B_thresh; \
187 } \
188 (x) = _B_x+1; \
189 } \
190 else \
191 (x) = 1; \
192 BIO_DECODE_EPILOGUE; \
193} while(0)
194
195#define BINARY_DECODE_L(x, b, count) \
196do { \
197 register unsigned long _B_x = 0; \
198 register unsigned long _B_b = (b); \
199 register int _B_i, _B_logofb, _B_thresh; \
200 BIO_DECODE_PROLOGUE; \
201 if (_B_b != 1) \
202 { \
203 CEILLOG_2(_B_b, _B_logofb); \
204 _B_thresh = (1<<_B_logofb) - _B_b; \
205 _B_logofb--; \
206 (count) += _B_logofb; \
207 for (_B_i=0; _B_i < _B_logofb; _B_i++) \
208 DECODE_ADD(_B_x); \
209 if (_B_x >= _B_thresh) \
210 { \
211 DECODE_ADD(_B_x); \
212 _B_x -= _B_thresh; \
213 (count)++; \
214 } \
215 (x) = _B_x+1; \
216 } \
217 else \
218 (x) = 1; \
219 BIO_DECODE_EPILOGUE; \
220} while(0)
221
222#define BINARY_LENGTH(x, b, count) \
223do { \
224 register unsigned long _B_x = (x); \
225 register unsigned long _B_b = (b); \
226 register int _B_nbits, _B_logofb, _B_thresh; \
227 POSITIVE(binary, _B_x); \
228 CEILLOG_2(_B_b, _B_logofb); \
229 _B_thresh = (1<<_B_logofb) - _B_b; \
230 if (--_B_x < _B_thresh) \
231 _B_nbits = _B_logofb-1; \
232 else \
233 _B_nbits = _B_logofb; \
234 (count) = _B_nbits; \
235} while(0)
236
237/****************************************************************************/
238
239
240
241
242#define GAMMA_ENCODE(x) \
243do { \
244 register unsigned long _B_xx = (x); \
245 register int _B_logofb; \
246 register int _B_nbits; \
247 BIO_ENCODE_PROLOGUE; \
248 POSITIVE(gamma, _B_xx); \
249 FLOORLOG_2(_B_xx, _B_logofb); \
250 _B_nbits = _B_logofb+1; \
251 while(_B_logofb--) ENCODE_BIT(0); \
252 while (--_B_nbits>=0) \
253 ENCODE_BIT((_B_xx>>_B_nbits) & 0x1); \
254 BIO_ENCODE_EPILOGUE; \
255} while (0)
256
257#define GAMMA_ENCODE_L(x, count) \
258do { \
259 register unsigned long _B_xx = (x); \
260 register int _B_logofb; \
261 register int _B_nbits; \
262 BIO_ENCODE_PROLOGUE; \
263 POSITIVE(gamma, _B_xx); \
264 FLOORLOG_2(_B_xx, _B_logofb); \
265 _B_nbits = _B_logofb+1; \
266 (count) += _B_logofb*2+1; \
267 while(_B_logofb--) ENCODE_BIT(0); \
268 while (--_B_nbits>=0) \
269 ENCODE_BIT((_B_xx>>_B_nbits) & 0x1); \
270 BIO_ENCODE_EPILOGUE; \
271} while (0)
272
273#define GAMMA_DECODE(x) \
274do { \
275 register unsigned long _B_xx = 1; \
276 register int _B_nbits = 0; \
277 BIO_DECODE_PROLOGUE; \
278 while(!DECODE_BIT) _B_nbits++; \
279 while (_B_nbits-- > 0) \
280 DECODE_ADD(_B_xx); \
281 (x) = _B_xx; \
282 BIO_DECODE_EPILOGUE; \
283} while (0)
284
285#define GAMMA_DECODE_L(x, count) \
286do { \
287 register unsigned long _B_xx = 1; \
288 register int _B_nbits = 0; \
289 BIO_DECODE_PROLOGUE; \
290 while(!DECODE_BIT) _B_nbits++; \
291 (count) += _B_nbits*2+1; \
292 while (_B_nbits-- > 0) \
293 DECODE_ADD(_B_xx); \
294 (x) = _B_xx; \
295 BIO_DECODE_EPILOGUE; \
296} while (0)
297
298#define GAMMA_LENGTH(x, count) \
299do { \
300 register unsigned long _B_xx = (x); \
301 register int _B_logofb; \
302 POSITIVE(gamma, _B_xx); \
303 FLOORLOG_2(_B_xx, _B_logofb); \
304 (count) = _B_logofb*2+1; \
305} while (0)
306
307
308
309/****************************************************************************/
310
311
312#define DELTA_ENCODE(x) \
313do { \
314 register unsigned long _B_xxx = (x); \
315 register int _B_logx; \
316 FLOORLOG_2(_B_xxx, _B_logx); \
317 GAMMA_ENCODE(_B_logx+1); \
318 BINARY_ENCODE(_B_xxx+1, 1<<_B_logx); \
319} while (0)
320
321#define DELTA_ENCODE_L(x, count) \
322do { \
323 register unsigned long _B_xxx = (x); \
324 register int _B_logx; \
325 FLOORLOG_2(_B_xxx, _B_logx); \
326 GAMMA_ENCODE_L(_B_logx+1, count); \
327 BINARY_ENCODE_L(_B_xxx+1, 1<<_B_logx, count); \
328} while (0)
329
330
331#define DELTA_DECODE(x) \
332do { \
333 register unsigned long _B_xxx; \
334 register int _B_logx; \
335 GAMMA_DECODE(_B_logx); _B_logx--; \
336 BINARY_DECODE(_B_xxx, 1<<_B_logx); _B_xxx--; \
337 (x) = _B_xxx + (1<<_B_logx); \
338} while (0)
339
340#define DELTA_DECODE_L(x, count) \
341do { \
342 register unsigned long _B_xxx; \
343 register int _B_logx; \
344 GAMMA_DECODE_L(_B_logx, count); _B_logx--; \
345 BINARY_DECODE_L(_B_xxx, 1<<_B_logx, count); _B_xxx--; \
346 (x) = _B_xxx + (1<<_B_logx); \
347} while (0)
348
349#define DELTA_LENGTH(x, count) \
350do { \
351 register unsigned long _B_xxx = (x); \
352 register int _B_logx, _B_dcount; \
353 FLOORLOG_2(_B_xxx, _B_logx); \
354 GAMMA_LENGTH(_B_logx+1, count); \
355 BINARY_LENGTH(_B_xxx+1, 1<<_B_logx, _B_dcount); \
356 (count) += _B_dcount; \
357} while (0)
358
359
360/****************************************************************************/
361
362
363
364
365#define ELIAS_ENCODE(x, b, s) \
366do { \
367 register unsigned long _B_xx = (x); \
368 register unsigned long _B_b = (b); \
369 register double _B_s = (s); \
370 register int _B_lower=1, _B_upper=1; \
371 register int _B_k=0; \
372 register double _B_pow=1.0; \
373 POSITIVE(elias, _B_xx); \
374 while (_B_xx>_B_upper) \
375 { \
376 _B_k++; \
377 _B_lower = _B_upper+1; \
378 _B_pow *= _B_s; \
379 _B_upper += _B_b*_B_pow; \
380 } \
381 UNARY_ENCODE(_B_k+1); \
382 BINARY_ENCODE(_B_xx-_B_lower+1, _B_upper-_B_lower+1); \
383} while (0)
384
385#define ELIAS_ENCODE_L(x, b, s, count) \
386do { \
387 register unsigned long _B_xx = (x); \
388 register unsigned long _B_b = (b); \
389 register double _B_s = (s); \
390 register int _B_lower=1, _B_upper=1; \
391 register int _B_k=0; \
392 register double _B_pow=1.0; \
393 POSITIVE(elias, _B_xx); \
394 while (_B_xx>_B_upper) \
395 { \
396 _B_k++; \
397 _B_lower = _B_upper+1; \
398 _B_pow *= _B_s; \
399 _B_upper += _B_b*_B_pow; \
400 } \
401 UNARY_ENCODE_L(_B_k+1, count); \
402 BINARY_ENCODE_L(_B_xx-_B_lower+1, _B_upper-_B_lower+1, count); \
403} while (0)
404
405#define ELIAS_DECODE(x, b, s) \
406do { \
407 register unsigned long _B_xx; \
408 register unsigned long _B_b = (b); \
409 register double _B_s = (s); \
410 register int _B_lower=1, _B_upper=1; \
411 register int _B_k; \
412 register double _B_pow=1.0; \
413 UNARY_DECODE(_B_k); _B_k--; \
414 while (_B_k--) \
415 { \
416 _B_lower = _B_upper+1; \
417 _B_pow *= _B_s; \
418 _B_upper += _B_b*_B_pow; \
419 } \
420 BINARY_DECODE(_B_xx, _B_upper-_B_lower+1); _B_xx--; \
421 POSITIVE(gamma, _B_xx+_B_lower); \
422 (x) = _B_xx+_B_lower; \
423} while (0)
424
425#define ELIAS_DECODE_L(x, b, s, count) \
426do { \
427 register unsigned long _B_xx; \
428 register unsigned long _B_b = (b); \
429 register double _B_s = (s); \
430 register int _B_lower=1, _B_upper=1; \
431 register int _B_k; \
432 register double _B_pow=1.0; \
433 UNARY_DECODE_L(_B_k, count); _B_k--; \
434 while (_B_k--) \
435 { \
436 _B_lower = _B_upper+1; \
437 _B_pow *= _B_s; \
438 _B_upper += _B_b*_B_pow; \
439 } \
440 BINARY_DECODE_L(_B_xx, _B_upper-_B_lower+1, count); _B_xx--; \
441 POSITIVE(gamma, _B_xx+_B_lower); \
442 (x) = _B_xx+_B_lower; \
443} while (0)
444
445#define ELIAS_LENGTH(x, b, s, count) \
446do { \
447 register unsigned long _B_xx = (x); \
448 register unsigned long _B_b = (b); \
449 register double _B_s = (s); \
450 register int _B_lower=1, _B_upper=1; \
451 register int _B_k=0, _B_ecount; \
452 register double _B_pow=1.0; \
453 POSITIVE(gamma, _B_xx); \
454 while (_B_xx>_B_upper) \
455 { \
456 _B_k++; \
457 _B_lower = _B_upper+1; \
458 _B_pow *= _B_s; \
459 _B_upper += _B_b*_B_pow; \
460 } \
461 UNARY_LENGTH(_B_k+1, count); \
462 BINARY_LENGTH(_B_xx-_B_lower+1, _B_upper-_B_lower+1, _B_ecount); \
463 (count) += _B_ecount; \
464} while (0)
465
466
467/****************************************************************************/
468
469
470#define BBLOCK_ENCODE(x, b) \
471do { \
472 register unsigned long _B_xx = (x); \
473 register unsigned long _B_bb = (b); \
474 register int _B_xdivb = 0; \
475 POSITIVE(bblock, _B_xx); \
476 _B_xx--; \
477 while (_B_xx >= _B_bb) \
478 { \
479 _B_xdivb++; \
480 _B_xx -= _B_bb; \
481 } \
482 UNARY_ENCODE(_B_xdivb+1); \
483 BINARY_ENCODE(_B_xx+1, _B_bb); \
484} while (0)
485
486#define BBLOCK_ENCODE_L(x, b, count) \
487do { \
488 register unsigned long _B_xx = (x); \
489 register unsigned long _B_bb = (b); \
490 register int _B_xdivb = 0; \
491 POSITIVE(bblock, _B_xx); \
492 _B_xx--; \
493 while (_B_xx >= _B_bb) \
494 { \
495 _B_xdivb++; \
496 _B_xx -= _B_bb; \
497 } \
498 UNARY_ENCODE_L(_B_xdivb+1, count); \
499 BINARY_ENCODE_L(_B_xx+1, _B_bb, count); \
500} while (0)
501
502#define BBLOCK_DECODE(x, b) \
503do { \
504 register unsigned long _B_x1, _B_xx = 0; \
505 register unsigned long _B_bb = (b); \
506 register int _B_xdivb; \
507 UNARY_DECODE(_B_xdivb); _B_xdivb--; \
508 while (_B_xdivb--) \
509 _B_xx += _B_bb; \
510 BINARY_DECODE(_B_x1, _B_bb); \
511 (x) = _B_xx+_B_x1; \
512} while (0)
513
514#define BBLOCK_DECODE_L(x, b, count) \
515do { \
516 register unsigned long _B_x1, _B_xx = 0; \
517 register unsigned long _B_bb = (b); \
518 register int _B_xdivb; \
519 UNARY_DECODE_L(_B_xdivb, count); _B_xdivb--; \
520 while (_B_xdivb--) \
521 _B_xx += _B_bb; \
522 BINARY_DECODE_L(_B_x1, _B_bb, count); \
523 (x) = _B_xx+_B_x1; \
524} while (0)
525
526#define BBLOCK_LENGTH(x, b, count) \
527do { \
528 register unsigned long _B_bcount, _B_xx = (x); \
529 register unsigned long _B_bb = (b); \
530 register int _B_xdivb = 0; \
531 POSITIVE(bblock, _B_xx); \
532 _B_xx--; \
533 while (_B_xx >= _B_bb) \
534 { \
535 _B_xdivb++; \
536 _B_xx -= _B_bb; \
537 } \
538 UNARY_LENGTH(_B_xdivb+1, count); \
539 BINARY_LENGTH(_B_xx+1, _B_bb, _B_bcount); \
540 (count) += _B_bcount; \
541} while (0)
542
543#endif
Note: See TracBrowser for help on using the repository browser.