bitwise.c

  1/*
  2Copyright 2011 Jun Wako <wakojun@gmail.com>
  3
  4This program is free software: you can redistribute it and/or modify
  5it under the terms of the GNU General Public License as published by
  6the Free Software Foundation, either version 2 of the License, or
  7(at your option) any later version.
  8
  9This program is distributed in the hope that it will be useful,
 10but WITHOUT ANY WARRANTY; without even the implied warranty of
 11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 12GNU General Public License for more details.
 13
 14You should have received a copy of the GNU General Public License
 15along with this program.  If not, see <http://www.gnu.org/licenses/>.
 16*/
 17
 18#include "util.h"
 19
 20// bit population - return number of on-bit
 21__attribute__((noinline)) uint8_t bitpop(uint8_t bits) {
 22    uint8_t c;
 23    for (c = 0; bits; c++)
 24        bits &= bits - 1;
 25    return c;
 26    /*
 27        const uint8_t bit_count[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
 28        return bit_count[bits>>4] + bit_count[bits&0x0F]
 29    */
 30}
 31
 32uint8_t bitpop16(uint16_t bits) {
 33    uint8_t c;
 34    for (c = 0; bits; c++)
 35        bits &= bits - 1;
 36    return c;
 37}
 38
 39uint8_t bitpop32(uint32_t bits) {
 40    uint8_t c;
 41    for (c = 0; bits; c++)
 42        bits &= bits - 1;
 43    return c;
 44}
 45
 46// most significant on-bit - return highest location of on-bit
 47// NOTE: return 0 when bit0 is on or all bits are off
 48__attribute__((noinline)) uint8_t biton(uint8_t bits) {
 49    uint8_t n = 0;
 50    if (bits >> 4) {
 51        bits >>= 4;
 52        n += 4;
 53    }
 54    if (bits >> 2) {
 55        bits >>= 2;
 56        n += 2;
 57    }
 58    if (bits >> 1) {
 59        bits >>= 1;
 60        n += 1;
 61    }
 62    return n;
 63}
 64
 65uint8_t biton16(uint16_t bits) {
 66    uint8_t n = 0;
 67    if (bits >> 8) {
 68        bits >>= 8;
 69        n += 8;
 70    }
 71    if (bits >> 4) {
 72        bits >>= 4;
 73        n += 4;
 74    }
 75    if (bits >> 2) {
 76        bits >>= 2;
 77        n += 2;
 78    }
 79    if (bits >> 1) {
 80        bits >>= 1;
 81        n += 1;
 82    }
 83    return n;
 84}
 85
 86uint8_t biton32(uint32_t bits) {
 87    uint8_t n = 0;
 88    if (bits >> 16) {
 89        bits >>= 16;
 90        n += 16;
 91    }
 92    if (bits >> 8) {
 93        bits >>= 8;
 94        n += 8;
 95    }
 96    if (bits >> 4) {
 97        bits >>= 4;
 98        n += 4;
 99    }
100    if (bits >> 2) {
101        bits >>= 2;
102        n += 2;
103    }
104    if (bits >> 1) {
105        bits >>= 1;
106        n += 1;
107    }
108    return n;
109}
110
111__attribute__((noinline)) uint8_t bitrev(uint8_t bits) {
112    bits = (bits & 0x0f) << 4 | (bits & 0xf0) >> 4;
113    bits = (bits & 0b00110011) << 2 | (bits & 0b11001100) >> 2;
114    bits = (bits & 0b01010101) << 1 | (bits & 0b10101010) >> 1;
115    return bits;
116}
117
118uint16_t bitrev16(uint16_t bits) {
119    bits = bitrev(bits & 0x00ff) << 8 | bitrev((bits & 0xff00) >> 8);
120    return bits;
121}
122
123uint32_t bitrev32(uint32_t bits) {
124    bits = (uint32_t)bitrev16(bits & 0x0000ffff) << 16 | bitrev16((bits & 0xffff0000) >> 16);
125    return bits;
126}