1<html><head><meta http-equiv="Content-Type" content="text/html; charset=ANSI_X3.4-1968"><title>bitmap_onto</title><meta name="generator" content="DocBook XSL Stylesheets V1.78.1"><link rel="home" href="index.html" title="The Linux Kernel API"><link rel="up" href="kernel-lib.html#idp1123213284" title="Bitmap Operations"><link rel="prev" href="API-bitmap-bitremap.html" title="bitmap_bitremap"><link rel="next" href="API-bitmap-fold.html" title="bitmap_fold"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center"><span class="phrase">bitmap_onto</span></th></tr><tr><td width="20%" align="left"><a accesskey="p" href="API-bitmap-bitremap.html">Prev</a> </td><th width="60%" align="center">Bitmap Operations</th><td width="20%" align="right"> <a accesskey="n" href="API-bitmap-fold.html">Next</a></td></tr></table><hr></div><div class="refentry"><a name="API-bitmap-onto"></a><div class="titlepage"></div><div class="refnamediv"><h2>Name</h2><p>bitmap_onto — 2 translate one bitmap relative to another 3 </p></div><div class="refsynopsisdiv"><h2>Synopsis</h2><div class="funcsynopsis"><table border="0" class="funcprototype-table" summary="Function synopsis" style="cellspacing: 0; cellpadding: 0;"><tr><td><code class="funcdef">void <b class="fsfunc">bitmap_onto </b>(</code></td><td>unsigned long * <var class="pdparam">dst</var>, </td></tr><tr><td> </td><td>const unsigned long * <var class="pdparam">orig</var>, </td></tr><tr><td> </td><td>const unsigned long * <var class="pdparam">relmap</var>, </td></tr><tr><td> </td><td>unsigned int <var class="pdparam">bits</var><code>)</code>;</td></tr></table><div class="funcprototype-spacer"> </div></div></div><div class="refsect1"><a name="idp1123348204"></a><h2>Arguments</h2><div class="variablelist"><dl class="variablelist"><dt><span class="term"><em class="parameter"><code>dst</code></em></span></dt><dd><p> 4 resulting translated bitmap 5 </p></dd><dt><span class="term"><em class="parameter"><code>orig</code></em></span></dt><dd><p> 6 original untranslated bitmap 7 </p></dd><dt><span class="term"><em class="parameter"><code>relmap</code></em></span></dt><dd><p> 8 bitmap relative to which translated 9 </p></dd><dt><span class="term"><em class="parameter"><code>bits</code></em></span></dt><dd><p> 10 number of bits in each of these bitmaps 11 </p></dd></dl></div></div><div class="refsect1"><a name="idp1123352924"></a><h2>Description</h2><p> 12 Set the n-th bit of <em class="parameter"><code>dst</code></em> iff there exists some m such that the 13 n-th bit of <em class="parameter"><code>relmap</code></em> is set, the m-th bit of <em class="parameter"><code>orig</code></em> is set, and 14 the n-th bit of <em class="parameter"><code>relmap</code></em> is also the m-th _set_ bit of <em class="parameter"><code>relmap</code></em>. 15 (If you understood the previous sentence the first time your 16 read it, you're overqualified for your current job.) 17 </p><p> 18 19 In other words, <em class="parameter"><code>orig</code></em> is mapped onto (surjectively) <em class="parameter"><code>dst</code></em>, 20 using the map { <n, m> | the n-th bit of <em class="parameter"><code>relmap</code></em> is the 21 m-th set bit of <em class="parameter"><code>relmap</code></em> }. 22 </p><p> 23 24 Any set bits in <em class="parameter"><code>orig</code></em> above bit number W, where W is the 25 weight of (number of set bits in) <em class="parameter"><code>relmap</code></em> are mapped nowhere. 26 In particular, if for all bits m set in <em class="parameter"><code>orig</code></em>, m >= W, then 27 <em class="parameter"><code>dst</code></em> will end up empty. In situations where the possibility 28 of such an empty result is not desired, one way to avoid it is 29 to use the <code class="function">bitmap_fold</code> operator, below, to first fold the 30 <em class="parameter"><code>orig</code></em> bitmap over itself so that all its set bits x are in the 31 range 0 <= x < W. The <code class="function">bitmap_fold</code> operator does this by 32 setting the bit (m % W) in <em class="parameter"><code>dst</code></em>, for each bit (m) set in <em class="parameter"><code>orig</code></em>. 33 </p><p> 34 35 Example [1] for <code class="function">bitmap_onto</code>: 36 Let's say <em class="parameter"><code>relmap</code></em> has bits 30-39 set, and <em class="parameter"><code>orig</code></em> has bits 37 1, 3, 5, 7, 9 and 11 set. Then on return from this routine, 38 <em class="parameter"><code>dst</code></em> will have bits 31, 33, 35, 37 and 39 set. 39 </p><p> 40 41 When bit 0 is set in <em class="parameter"><code>orig</code></em>, it means turn on the bit in 42 <em class="parameter"><code>dst</code></em> corresponding to whatever is the first bit (if any) 43 that is turned on in <em class="parameter"><code>relmap</code></em>. Since bit 0 was off in the 44 above example, we leave off that bit (bit 30) in <em class="parameter"><code>dst</code></em>. 45 </p><p> 46 47 When bit 1 is set in <em class="parameter"><code>orig</code></em> (as in the above example), it 48 means turn on the bit in <em class="parameter"><code>dst</code></em> corresponding to whatever 49 is the second bit that is turned on in <em class="parameter"><code>relmap</code></em>. The second 50 bit in <em class="parameter"><code>relmap</code></em> that was turned on in the above example was 51 bit 31, so we turned on bit 31 in <em class="parameter"><code>dst</code></em>. 52 </p><p> 53 54 Similarly, we turned on bits 33, 35, 37 and 39 in <em class="parameter"><code>dst</code></em>, 55 because they were the 4th, 6th, 8th and 10th set bits 56 set in <em class="parameter"><code>relmap</code></em>, and the 4th, 6th, 8th and 10th bits of 57 <em class="parameter"><code>orig</code></em> (i.e. bits 3, 5, 7 and 9) were also set. 58 </p><p> 59 60 When bit 11 is set in <em class="parameter"><code>orig</code></em>, it means turn on the bit in 61 <em class="parameter"><code>dst</code></em> corresponding to whatever is the twelfth bit that is 62 turned on in <em class="parameter"><code>relmap</code></em>. In the above example, there were 63 only ten bits turned on in <em class="parameter"><code>relmap</code></em> (30..39), so that bit 64 11 was set in <em class="parameter"><code>orig</code></em> had no affect on <em class="parameter"><code>dst</code></em>. 65 </p><p> 66 67 Example [2] for <code class="function">bitmap_fold</code> + <code class="function">bitmap_onto</code>: 68 Let's say <em class="parameter"><code>relmap</code></em> has these ten bits set: 69 40 41 42 43 45 48 53 61 74 95 70 (for the curious, that's 40 plus the first ten terms of the 71 Fibonacci sequence.) 72 </p><p> 73 74 Further lets say we use the following code, invoking 75 <code class="function">bitmap_fold</code> then bitmap_onto, as suggested above to 76 avoid the possibility of an empty <em class="parameter"><code>dst</code></em> result: 77 </p><p> 78 79 unsigned long *tmp; // a temporary bitmap's bits 80 </p><p> 81 82 bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits); 83 bitmap_onto(dst, tmp, relmap, bits); 84 </p><p> 85 86 Then this table shows what various values of <em class="parameter"><code>dst</code></em> would be, for 87 various <em class="parameter"><code>orig</code></em>'s. I list the zero-based positions of each set bit. 88 The tmp column shows the intermediate result, as computed by 89 using <code class="function">bitmap_fold</code> to fold the <em class="parameter"><code>orig</code></em> bitmap modulo ten 90 (the weight of <em class="parameter"><code>relmap</code></em>). 91 </p><p> 92 93 <em class="parameter"><code>orig</code></em> tmp <em class="parameter"><code>dst</code></em> 94 0 0 40 95 1 1 41 96 9 9 95 97 10 0 40 (*) 98 1 3 5 7 1 3 5 7 41 43 48 61 99 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45 100 0 9 18 27 0 9 8 7 40 61 74 95 101 0 10 20 30 0 40 102 0 11 22 33 0 1 2 3 40 41 42 43 103 0 12 24 36 0 2 4 6 40 42 45 53 104 78 102 211 1 2 8 41 42 74 (*) 105 </p><p> 106 107 (*) For these marked lines, if we hadn't first done <code class="function">bitmap_fold</code> 108 into tmp, then the <em class="parameter"><code>dst</code></em> result would have been empty. 109 </p><p> 110 111 If either of <em class="parameter"><code>orig</code></em> or <em class="parameter"><code>relmap</code></em> is empty (no set bits), then <em class="parameter"><code>dst</code></em> 112 will be returned empty. 113 </p><p> 114 115 If (as explained above) the only set bits in <em class="parameter"><code>orig</code></em> are in positions 116 m where m >= W, (where W is the weight of <em class="parameter"><code>relmap</code></em>) then <em class="parameter"><code>dst</code></em> will 117 once again be returned empty. 118 </p><p> 119 120 All bits in <em class="parameter"><code>dst</code></em> not set by the above rule are cleared. 121</p></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="API-bitmap-bitremap.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="kernel-lib.html#idp1123213284">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="API-bitmap-fold.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top"><span class="phrase">bitmap_bitremap</span> </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> <span class="phrase">bitmap_fold</span></td></tr></table></div></body></html> 122