Systemnahe Programmierung in C: Bitstring-Operationen
| Systemnahe Programmierung in C: Bitstring-Operationen |
|
|
1/* Macros and functions for bitstring processing */
2
3/* these are the basic operations for
4 implementing "big-endian patricia trees"
5 for efficient maps with unsigned int's as keys
6*/
7
8#include <limits.h>
9
10typedef unsigned long int BitString;
11
12/* a Prefix of a BitString is represented
13 by a BitString where the least significant
14 bits are cleared
15*/
16typedef BitString Prefix;
17
18/* a Mask (in this context) is a BitString
19 with a single bit set. A Mask will be used
20 to specify the length of a Prefix. The bit
21 position of the mask determines the 1. bit
22 not included in the prefix
23*/
24typedef BitString Mask;
25
26#define LEN_BITSTRING (CHAR_BIT * sizeof (BitString))
27
28
29#define check(i) ( (BitString)(i) < LEN_BITSTRING )
30
31#define emptyBitString ( (BitString)0 )
32
33#define singleton(i) ( ((BitString)1) << (i) )
34
35/* in a Mask a single bit is set */
36
37#define invMask(m) ( (m) != emptyBitString \
38 && \
39 ((m) ^ ((m) & (~(m) + 1))) == emptyBitString \
40 )
41
42/*----------------------------------------*/
43
44extern void printBitString (BitString bs);
45
46extern void printPrefix(Prefix p, Mask m);
47
48/* mask for longest 0-prefix
49 basic operation, needed by commonPrefixMask
50 */
51extern Mask zeroPrefix(BitString bs);
52
53/* faster version of zeroPrefix */
54extern Mask zeroPrefixFast(BitString bs);
55
56/* compute common prefix length represented by a mask*/
57extern Mask commonPrefixMask(BitString bs1, BitString bs2);
58
59/* get a prefix of a given length (represented by a mask) */
60extern Prefix getPrefix(BitString bs, Mask m);
61
62/* compare a prefix of a bitstring with a given prefix */
63extern int matchPrefix(BitString bs, Prefix p, Mask m);
64
|
|
1#include <stdio.h>
2#include <assert.h>
3
4#include "BitString.h"
5
6/*----------------------------------------*/
7
8void
9printBitString (BitString bs) {
10 int i = LEN_BITSTRING;
11 while (i > 0) {
12 --i;
13 printf ("%c", (char)(((bs >> i) & 0x1) + '0'));
14 }
15}
16
17void
18printPrefix(Prefix p, Mask m) {
19 int i = LEN_BITSTRING;
20 while ((singleton(i - 1) & m) == 0) {
21 --i;
22 printf ("%c", (char)(((p >> i) & 0x1) + '0'));
23 }
24}
25
26/*----------------------------------------*/
27
28Mask zeroPrefix(BitString bs) {
29 int i = 1;
30 while (i < LEN_BITSTRING) {
31 bs = bs | (bs >> i);
32 i *= 2;
33 }
34 return bs ^ (bs >> 1);
35}
36
37/* optimization: loop unrolling
38 (here for 32- and 64-bit architectures)
39*/
40Mask zeroPrefixFast(BitString bs) {
41 register BitString bs1 = bs;
42
43 bs1 |= bs1 >> 1;
44 bs1 |= bs1 >> 2;
45 bs1 |= bs1 >> 4;
46 bs1 |= bs1 >> 8;
47 bs1 |= bs1 >> 16;
48
49#if (LEN_BITSTING > 32) // 64 bit architecture
50 bs1 |= bs1 >> 32;
51#endif
52
53 return bs1 ^ (bs1 >> 1);
54}
55
56Mask commonPrefixMask(BitString bs1, BitString bs2) {
57 return
58 zeroPrefixFast(bs1 ^ bs2);
59}
60
61Prefix getPrefix(BitString bs, Mask m) {
62 assert(invMask(m));
63 return
64 bs & (~(m - 1) ^ m);
65}
66
67int matchPrefix(BitString bs, Prefix p, Mask m) {
68 return
69 getPrefix(bs, m) == p;
70}
|
| Letzte Änderung: 11.11.2013 | © Prof. Dr. Uwe Schmidt |
