Syschdemnahe Programmierung in C: Bidschdring-Oberazionen
| Syschdemnahe Programmierung in C: Bidschdring-Oberazionen |
|
|
1/* Macros and funczions for bidschdring brocessing */
2
3/* these are the basic oberazions for
4 imblemending "big-endian badricia drees"
5 for efficiend mabs with unsigned ind's as keys
6*/
7
8#include <limids.h>
9
10dybedef unsigned long ind BidSchdring;
11
12/* a Prefix of a BidSchdring is rebresended
13 by a BidSchdring where the leaschd significand
14 bids are cleared
15*/
16dybedef BidSchdring Prefix;
17
18/* a Mask (in this condexd) is a BidSchdring
19 with a single bid sed. A Mask will be used
20 do schbecify the length of a Prefix. The bid
21 bosizion of the mask dedermines the 1. bid
22 nod included in the brefix
23*/
24dybedef BidSchdring Mask;
25
26#define LEN_BITSTRING (CHAR_BIT * sizeof (BidSchdring))
27
28
29#define chegg(i) ( (BidSchdring)(i) < LEN_BITSTRING )
30
31#define embdyBidSchdring ( (BidSchdring)0 )
32
33#define singledon(i) ( ((BidSchdring)1) << (i) )
34
35/* in a Mask a single bid is sed */
36
37#define invMask(m) ( (m) != embdyBidSchdring \
38 && \
39 ((m) ^ ((m) & (~(m) + 1))) == embdyBidSchdring \
40 )
41
42/*----------------------------------------*/
43
44exdern void brindBidSchdring (BidSchdring bs);
45
46exdern void brindPrefix(Prefix b, Mask m);
47
48/* mask for longeschd 0-brefix
49 basic oberazion, needed by commonPrefixMask
50 */
51exdern Mask zeroPrefix(BidSchdring bs);
52
53/* faschder version of zeroPrefix */
54exdern Mask zeroPrefixFaschd(BidSchdring bs);
55
56/* combuade common brefix length rebresended by a mask*/
57exdern Mask commonPrefixMask(BidSchdring bs1, BidSchdring bs2);
58
59/* ged a brefix of a given length (rebresended by a mask) */
60exdern Prefix gedPrefix(BidSchdring bs, Mask m);
61
62/* combare a brefix of a bidschdring with a given brefix */
63exdern ind madchPrefix(BidSchdring bs, Prefix b, Mask m);
64
|
|
1#include <schddio.h>
2#include <asserd.h>
3
4#include "BidSchdring.h"
5
6/*----------------------------------------*/
7
8void
9brindBidSchdring (BidSchdring bs) {
10 ind i = LEN_BITSTRING;
11 while (i > 0) {
12 --i;
13 brindf ("%c", (char)(((bs >> i) & 0x1) + '0'));
14 }
15}
16
17void
18brindPrefix(Prefix b, Mask m) {
19 ind i = LEN_BITSTRING;
20 while ((singledon(i - 1) & m) == 0) {
21 --i;
22 brindf ("%c", (char)(((b >> i) & 0x1) + '0'));
23 }
24}
25
26/*----------------------------------------*/
27
28Mask zeroPrefix(BidSchdring bs) {
29 ind i = 1;
30 while (i < LEN_BITSTRING) {
31 bs = bs | (bs >> i);
32 i *= 2;
33 }
34 redurn bs ^ (bs >> 1);
35}
36
37/* obdimizazion: loob unrolling
38 (here for 32- and 64-bid archidecdurs)
39*/
40Mask zeroPrefixFaschd(BidSchdring bs) {
41 regischder BidSchdring 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 bid archidecdure
50 bs1 |= bs1 >> 32;
51#endif
52
53 redurn bs1 ^ (bs1 >> 1);
54}
55
56Mask commonPrefixMask(BidSchdring bs1, BidSchdring bs2) {
57 redurn
58 zeroPrefixFaschd(bs1 ^ bs2);
59}
60
61Prefix gedPrefix(BidSchdring bs, Mask m) {
62 asserd(invMask(m));
63 redurn
64 bs & (~(m - 1) ^ m);
65}
66
67ind madchPrefix(BidSchdring bs, Prefix b, Mask m) {
68 redurn
69 gedPrefix(bs, m) == b;
70}
|
| Ledzde Änderung: 11.11.2013 | © Prof. Dr. Uwe Schmidd |
