1BITMAP_ONTO(9) Basic Kernel Library Functions BITMAP_ONTO(9)
2
6 bitmap_onto - translate one bitmap relative to another
7
9 void bitmap_onto(unsigned long * dst, const unsigned long * orig,
10 const unsigned long * relmap, int bits);
11
13 dst
14 resulting translated bitmap
15 orig
17 original untranslated bitmap
18 relmap
20 bitmap relative to which translated
21 bits
23 number of bits in each of these bitmaps
24
26 Set the n-th bit of dst iff there exists some m such that the n-th bit
27 of relmap is set, the m-th bit of orig is set, and the n-th bit of
28 relmap is also the m-th _set_ bit of relmap. (If you understood the
29 previous sentence the first time your read it, you're overqualified for
30 your current job.)
31 In other words, orig is mapped onto (surjectively) dst, using the the
33 map { <n, m> | the n-th bit of relmap is the m-th set bit of relmap }.
34 Any set bits in orig above bit number W, where W is the weight of
36 (number of set bits in) relmap are mapped nowhere. In particular, if
37 for all bits m set in orig, m >= W, then dst will end up empty. In
38 situations where the possibility of such an empty result is not
39 desired, one way to avoid it is to use the bitmap_fold operator, below,
40 to first fold the orig bitmap over itself so that all its set bits x
41 are in the range 0 <= x < W. The bitmap_fold operator does this by
42 setting the bit (m % W) in dst, for each bit (m) set in orig.
43 Example [1] for bitmap_onto: Let's say relmap has bits 30-39 set, and
45 orig has bits 1, 3, 5, 7, 9 and 11 set. Then on return from this
46 routine, dst will have bits 31, 33, 35, 37 and 39 set.
47 When bit 0 is set in orig, it means turn on the bit in dst
49 corresponding to whatever is the first bit (if any) that is turned on
50 in relmap. Since bit 0 was off in the above example, we leave off that
51 bit (bit 30) in dst.
52 When bit 1 is set in orig (as in the above example), it means turn on
54 the bit in dst corresponding to whatever is the second bit that is
55 turned on in relmap. The second bit in relmap that was turned on in the
56 above example was bit 31, so we turned on bit 31 in dst.
57 Similarly, we turned on bits 33, 35, 37 and 39 in dst, because they
59 were the 4th, 6th, 8th and 10th set bits set in relmap, and the 4th,
60 6th, 8th and 10th bits of orig (i.e. bits 3, 5, 7 and 9) were also set.
61 When bit 11 is set in orig, it means turn on the bit in dst
63 corresponding to whatever is the twelth bit that is turned on in
64 relmap. In the above example, there were only ten bits turned on in
65 relmap (30..39), so that bit 11 was set in orig had no affect on dst.
66 Example [2] for bitmap_fold + bitmap_onto: Let's say relmap has these
68 ten bits set: 40 41 42 43 45 48 53 61 74 95 (for the curious, that's 40
69 plus the first ten terms of the Fibonacci sequence.)
70 Further lets say we use the following code, invoking bitmap_fold then
72 bitmap_onto, as suggested above to avoid the possitility of an empty
73 dst result:
74 unsigned long *tmp; // a temporary bitmap's bits
76 bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
78 bitmap_onto(dst, tmp, relmap, bits);
79 Then this table shows what various values of dst would be, for various
81 orig's. I list the zero-based positions of each set bit. The tmp column
82 shows the intermediate result, as computed by using bitmap_fold to fold
83 the orig bitmap modulo ten (the weight of relmap).
84 orig tmp dst 0 0 40 1 1 41 9 9 95 10 0 40 (*) 1 3 5 7 1 3 5 7 41 43 48
86 61 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45 0 9 18 27 0 9 8 7 40 61 74 95 0
87 10 20 30 0 40 0 11 22 33 0 1 2 3 40 41 42 43 0 12 24 36 0 2 4 6 40 42
88 45 53 78 102 211 1 2 8 41 42 74 (*)
89 (*) For these marked lines, if we hadn't first done bitmap_fold into
91 tmp, then the dst result would have been empty.
92 If either of orig or relmap is empty (no set bits), then dst will be
94 returned empty.
95 If (as explained above) the only set bits in orig are in positions m
97 where m >= W, (where W is the weight of relmap) then dst will once
98 again be returned empty.
99 All bits in dst not set by the above rule are cleared.
101
103Kernel Hackers Manual 2.6. November 2011 BITMAP_ONTO(9)