lib/ext2fs/bitops.c

   1 /*
   2  * bitops.c --- Bitmap frobbing code.  See bitops.h for the inlined
   3  *      routines.
   4  *
   5  * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o.
   6  *
   7  * %Begin-Header%
   8  * This file may be redistributed under the terms of the GNU Library
   9  * General Public License, version 2.
  10  * %End-Header%
  11  */
  12
  13 #include "config.h"
  14 #include <stdio.h>
  15 #if HAVE_SYS_TYPES_H
  16 #include <sys/types.h>
  17 #endif
  18
  19 #include "ext2_fs.h"
  20 #include "ext2fs.h"
  21
  22 #ifndef _EXT2_HAVE_ASM_BITOPS_
  23
  24 /*
  25  * For the benefit of those who are trying to port Linux to another
  26  * architecture, here are some C-language equivalents.  You should
  27  * recode these in the native assembly language, if at all possible.
  28  *
  29  * C language equivalents written by Theodore Ts'o, 9/26/92.
  30  * Modified by Pete A. Zaitcev 7/14/95 to be portable to big endian
  31  * systems, as well as non-32 bit systems.
  32  */
  33
  34 int ext2fs_set_bit(unsigned int nr,void * addr)
  35 {
  36         int             mask, retval;
  37         unsigned char   *ADDR = (unsigned char *) addr;
  38
  39         ADDR += nr >> 3;
  40         mask = 1 << (nr & 0x07);
  41         retval = mask & *ADDR;
  42         *ADDR |= mask;
  43         return retval;
  44 }
  45
  46 int ext2fs_clear_bit(unsigned int nr, void * addr)
  47 {
  48         int             mask, retval;
  49         unsigned char   *ADDR = (unsigned char *) addr;
  50
  51         ADDR += nr >> 3;
  52         mask = 1 << (nr & 0x07);
  53         retval = mask & *ADDR;
  54         *ADDR &= ~mask;
  55         return retval;
  56 }
  57
  58 int ext2fs_test_bit(unsigned int nr, const void * addr)
  59 {
  60         int                     mask;
  61         const unsigned char     *ADDR = (const unsigned char *) addr;
  62
  63         ADDR += nr >> 3;
  64         mask = 1 << (nr & 0x07);
  65         return (mask & *ADDR);
  66 }
  67
  68 #endif  /* !_EXT2_HAVE_ASM_BITOPS_ */
  69
  70 void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg,
  71                         const char *description)
  72 {
  73 #ifndef OMIT_COM_ERR
  74         if (description)
  75                 com_err(0, errcode, "#%lu for %s", arg, description);
  76         else
  77                 com_err(0, errcode, "#%lu", arg);
  78 #endif
  79 }
  80
  81 /*
  82  * C-only 64 bit ops.
  83  */
  84
  85 int ext2fs_set_bit64(__u64 nr, void * addr)
  86 {
  87         int             mask, retval;
  88         unsigned char   *ADDR = (unsigned char *) addr;
  89
  90         ADDR += nr >> 3;
  91         mask = 1 << (nr & 0x07);
  92         retval = mask & *ADDR;
  93         *ADDR |= mask;
  94         return retval;
  95 }
  96
  97 int ext2fs_clear_bit64(__u64 nr, void * addr)
  98 {
  99         int             mask, retval;
 100         unsigned char   *ADDR = (unsigned char *) addr;
 101
 102         ADDR += nr >> 3;
 103         mask = 1 << (nr & 0x07);
 104         retval = mask & *ADDR;
 105         *ADDR &= ~mask;
 106         return retval;
 107 }
 108
 109 int ext2fs_test_bit64(__u64 nr, const void * addr)
 110 {
 111         int                     mask;
 112         const unsigned char     *ADDR = (const unsigned char *) addr;
 113
 114         ADDR += nr >> 3;
 115         mask = 1 << (nr & 0x07);
 116         return (mask & *ADDR);
 117 }
 118
 119 static unsigned int popcount8(unsigned int w)
 120 {
 121         unsigned int res = w - ((w >> 1) & 0x55);
 122         res = (res & 0x33) + ((res >> 2) & 0x33);
 123         return (res + (res >> 4)) & 0x0F;
 124 }
 125
 126 static unsigned int popcount32(unsigned int w)
 127 {
 128         unsigned int res = w - ((w >> 1) & 0x55555555);
 129         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
 130         res = (res + (res >> 4)) & 0x0F0F0F0F;
 131         res = res + (res >> 8);
 132         return (res + (res >> 16)) & 0x000000FF;
 133 }
 134
 135 unsigned int ext2fs_bitcount(const void *addr, unsigned int nbytes)
 136 {
 137         const unsigned char *cp = addr;
 138         const __u32 *p;
 139         unsigned int res = 0;
 140
 141         while (((((uintptr_t) cp) & 3) != 0) && (nbytes > 0)) {
 142                 res += popcount8(*cp++);
 143                 nbytes--;
 144         }
 145         p = (const __u32 *) cp;
 146
 147         while (nbytes > 4) {
 148                 res += popcount32(*p++);
 149                 nbytes -= 4;
 150         }
 151         cp = (const unsigned char *) p;
 152
 153         while (nbytes > 0) {
 154                 res += popcount8(*cp++);
 155                 nbytes--;
 156         }
 157         return res;
 158 }