fuchsia / fuchsia / eb50e07bc90baedf041d7def6479a9b91f880d73 / . / zircon / kernel / lib / ktl / popcount.cc

// Copyright 2019 The Fuchsia Authors | |

// | |

// Use of this source code is governed by a MIT-style | |

// license that can be found in the LICENSE file or at | |

// https://opensource.org/licenses/MIT | |

#include <stdint.h> | |

// When the compiler doesn't inline __builtin_popcount{,l}, it calls these. | |

extern "C" int __popcountsi2(uint32_t val) { | |

// Implement a log2(bits) popcount, with a few tricks to save some | |

// instructions. | |

// | |

// The general idea here is to simply add up the bits in the word in | |

// parallel, storing intermediate results in different bit positions in | |

// the word as we go, and eventually arriving at a sum which is the | |

// popcount of the word. | |

// | |

// For example, consider an 8 bit integer written as | |

// | |

// b7 b6 b5 b4 b3 b2 b1 b0 | |

// | |

// Each of the bits in the word represent a partial sum that, when added | |

// together, produce our result. We can compute... | |

// | |

// ( | |

// b7 b6 b5 b4 b3 b2 b1 b0 & | |

// 0 1 0 1 0 1 0 1 = | |

// 0 b6 0 b4 0 b2 0 b0 | |

// ) + ( | |

// b7 b6 b5 b4 b3 b2 b1 b0 >> 1 = | |

// 0 b7 b6 b5 b4 b3 b2 b1 & | |

// 0 1 0 1 0 1 0 1 = | |

// 0 b7 0 b5 0 b3 0 b1 | |

// ) = | |

// b7+b6 b5+b4 b3+b2 b1+b0 | |

// | |

// And now we have 4 partial sums, each of which takes two bits of | |

// storage instead of one. Repeating this process with appropriate | |

// masks and shifts will eventually give us the answer we are looking | |

// for. After the next step, we will have partial sums which require 3 | |

// bits of storage, but aligned to 4 bit boundaries; so... | |

// | |

// 0 (b7+b6+b5+b4) 0 (b3+b2+b1+b0) | |

// | |

// After the last step, we will get the final sum stored in 4 bits, with | |

// guaranteed 0s for the upper bits. | |

// aligned to ... | |

// | |

// 0 0 0 0 (b7+b6+b5+b4+b3+b2+b1+b0) | |

// | |

// While this is the general idea, it turns out that we only need to | |

// follow this exact process during step #2. For each of the other | |

// steps (there will be 5 for a 32 bit integer) we can shave a few | |

// cycles by taking advantage of some of the particular properties of | |

// each step. See the comments below. | |

constexpr uint32_t mask1 = 0x55555555; | |

constexpr uint32_t mask2 = 0x33333333; | |

constexpr uint32_t mask3 = 0x0F0F0F0F; | |

constexpr uint32_t mult1 = 0x01010101; | |

// Step 1: | |

// While we could compute (val & mask) + ((val >> 1) & mask), we can | |

// actually save one of the mask operations by subtracting instead of | |

// adding. Consider the following truth table... | |

// | |

// In | >>1 | & | - | | |

// X00 | XX0 | X00 | X00 | | |

// X01 | XX0 | X00 | X01 | | |

// X10 | XX1 | X01 | X01 | | |

// X11 | XX1 | X01 | X10 | | |

// | |

val = val - ((val >> 1) & mask1); | |

// Step 2: | |

// This is simply the operation described in the overview, adding a | |

// bunch of 2 bit partials to produce a 3 bit result, but which is | |

// aligned on 4 bit boundaries (where the MSB of each 4 bit nibble is | |

// guaranteed to be 0) | |

val = (val & mask2) + ((val >> 2) & mask2); | |

// Step 3: | |

// Again, we can save a mask operation here. This time, it is because | |

// the we know that all bit positions ((i * 4) + 3) are guaranteed to be | |

// zero. We can simply shift by 4 and add the partial sums. Any | |

// overflow will go into the ((i * 4) + 3) position and not interfere | |

// with any of the other partial sums. | |

val = (val + (val >> 4)) & mask3; | |

// Step 4 + 5: | |

// Finally, we can combine steps 4 and 5 using a multiply. We have 4 | |

// remaining partial sums, each of which is contained in 4 bits and | |

// aligned to 8 bit boundaries (with 4 bits of zero in-between each | |

// sum). Now, we have enough space that if we could perform all 4 sums | |

// at once, we know that the result would fit in (at most) 6 bits, which | |

// easily fits in our 8 bits of space. | |

// | |

// At its heart, multiplying is the equivalent of repeated shifting, and | |

// conditional adding. IOW - if I multiply by 0101b, it is basically | |

// the same as saying "shift X left by 0, then add that to shift X left | |

// by 2" (because bits 0 and bits 2 are the only bits set). | |

// | |

// So, we have, 0x0A0B0C0D, and want to compute (A+B+C+D). Multiplying | |

// our register by 0x01010101 basically does this for us. We are | |

// summing our register shifted left by 0 (A), 8 (B), 16 (C) and 24 (D), | |

// which puts A+B+C+D into the upper 8 bits of the register. The lower | |

// 24 bits are junk, but we know (because of the 0s which separate A-D) | |

// that this junk is not going to overflow into our result. All we need | |

// to do is right shift by 24, and we are done. | |

return (val * mult1) >> 24; | |

} | |

extern "C" int __popcountdi2(uint64_t val) { | |

// See notes above for how this works. The 64 bit version of this is | |

// identical to the 32 bit version, the only difference is that during | |

// the final stage, we use the multiply trick to combine steps 4, 5, and | |

// 6 to sum all 8 4-bit partial sums at once, fitting the result into a | |

// 7 bit value. | |

constexpr uint64_t mask1 = 0x5555555555555555; | |

constexpr uint64_t mask2 = 0x3333333333333333; | |

constexpr uint64_t mask3 = 0x0F0F0F0F0F0F0F0F; | |

constexpr uint64_t mult1 = 0x0101010101010101; | |

val = val - ((val >> 1) & mask1); | |

val = (val & mask2) + ((val >> 2) & mask2); | |

val = (val + (val >> 4)) & mask3; | |

return static_cast<int>((val * mult1) >> 56); | |

} |