title: How do I sum the four 2-bit bitfields in a single 8-bit byte?
body: <p>I have four 2-bit bitfields stored in a single byte.  Each bitfield can thus represent 0, 1, 2, or 3.  For example, here are the 4 possible values where the first 3 bitfields are zero:</p>
  <pre><code>00 00 00 00 = 0 0 0 0
  00 00 00 01 = 0 0 0 1
  00 00 00 10 = 0 0 0 2
  00 00 00 11 = 0 0 0 3
  </code></pre>
  <p>I'd like an efficient way to sum the four bitfields.  For example:</p>
  <pre><code>11 10 01 00 = 3 + 2 + 1 + 0 = 6
  </code></pre>
  <p>A 8-bit lookup table on a modern Intel x64 CPU takes 4 cycles to return an answer from L1.  It seems like there should be some way to calculate the answer faster than that. 3 cycles gives about room for 6-12 simple bit operations.  As a starter, the straightforward mask and shift look like it will take 5 cycles on Sandy Bridge:</p>
  <p>Assuming the bit fields are: <code>d c b a</code>, and that mask is: <code>00 00 00 11</code></p>
  <p>Clarifying with help from Ira:  This presumes that <code>a</code>, <code>b</code>, <code>c</code>, and <code>d</code> are identical and have all been set to the initial <code>byte</code>.  Oddly, I think I can do this for free.  Since I can do 2 loads per cycle, instead of loading <code>byte</code> once, I can just load it four times: <code>a</code> and <code>d</code> on the first cycle, <code>b</code> and <code>c</code> on the second.  The second two loads will be delayed one cycle, but I don't need them until the second cycle.  The splits below represent how things should break into separate cycles.</p>
  <pre><code>a = *byte
  d = *byte
  
  b = *byte
  c = *byte
  
  latency
  
  latency
  
  a &amp;= mask
  d &gt;&gt;= 6
  
  b &gt;&gt;= 2
  c &gt;&gt;= 4
  a += d
  
  b &amp;= mask
  c &amp;= mask
  
  b += c
  
  a += b
  </code></pre>
  <p>A different encoding for the bitfields to make the logic easier would actually be fine, so long as it fits within a single byte and maps one-to-one with this scheme somehow.  Dropping to assembly is also fine.  Current target is Sandy Bridge, but targeting Haswell or beyond is fine too.</p>
  <p>Application and motivation:  I'm trying to make an open-source variable bit decompression routine go faster.  Each bitfield represents the compressed length of each of the four integers that follow.  I need the sum to know how many bytes I need to jump to get to the next group of four.  The current loop takes 10 cycles, with 5 of that coming the lookup I'm trying to avoid.  Shaving off a cycle would be ~10% improvement.</p>
  <h2>Edit:</h2>
  <p>Originally I said &quot;8 cycles&quot;, but as Evgeny points out below I was wrong. As Evgeny points out, the only time there is an indirect 4 cycle load is if loading from the first 2K of system memory without using an index register.  A correct list of latencies can be found in the <a href="http://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf" rel="nofollow noreferrer">Intel Architecture Optimization Manual</a> Section 2.12</p>
  <pre><code>&gt;    Data Type       (Base + Offset) &gt; 2048   (Base + Offset) &lt; 2048 
  &gt;                     Base + Index [+ Offset]
  &gt;     Integer                5 cycles               4 cycles
  &gt;     MMX, SSE, 128-bit AVX  6 cycles               5 cycles
  &gt;     X87                    7 cycles               6 cycles 
  &gt;     256-bit AVX            7 cycles               7 cycles
  </code></pre>
  <h2>Edit:</h2>
  <p>I think this is how Ira's solution below would break into cycles.  I think it also takes 5 cycles of work post load.</p>
  <pre><code>a = *byte
  b = *byte
  
  latency
  
  latency 
  
  latency
  
  a &amp;= 0x33
  b &gt;&gt;= 2
  
  b &amp;= 0x33
  c = a
  
  a += b
  c += b
  
  a &amp;= 7
  c &gt;&gt;= 4
  
  a += c 
  </code></pre>