Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 1 | /* |
| 2 | * bitops.c --- Bitmap frobbing code. See bitops.h for the inlined |
| 3 | * routines. |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 4 | * |
Theodore Ts'o | 21c84b7 | 1997-04-29 16:15:03 +0000 | [diff] [blame] | 5 | * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o. |
| 6 | * |
| 7 | * %Begin-Header% |
Theodore Ts'o | 543547a | 2010-05-17 21:31:56 -0400 | [diff] [blame] | 8 | * This file may be redistributed under the terms of the GNU Library |
| 9 | * General Public License, version 2. |
Theodore Ts'o | 21c84b7 | 1997-04-29 16:15:03 +0000 | [diff] [blame] | 10 | * %End-Header% |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 11 | */ |
| 12 | |
Theodore Ts'o | d1154eb | 2011-09-18 17:34:37 -0400 | [diff] [blame] | 13 | #include "config.h" |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 14 | #include <stdio.h> |
Theodore Ts'o | 1d2ff46 | 1997-10-19 23:00:21 +0000 | [diff] [blame] | 15 | #if HAVE_SYS_TYPES_H |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 16 | #include <sys/types.h> |
Theodore Ts'o | 1d2ff46 | 1997-10-19 23:00:21 +0000 | [diff] [blame] | 17 | #endif |
Theodore Ts'o | f3db356 | 1997-04-26 13:34:30 +0000 | [diff] [blame] | 18 | |
Theodore Ts'o | b5abe6f | 1998-01-19 14:47:53 +0000 | [diff] [blame] | 19 | #include "ext2_fs.h" |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 20 | #include "ext2fs.h" |
| 21 | |
Theodore Ts'o | f3db356 | 1997-04-26 13:34:30 +0000 | [diff] [blame] | 22 | #ifndef _EXT2_HAVE_ASM_BITOPS_ |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 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 assmebly language, if at all possible. |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 28 | * |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 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. |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 32 | */ |
| 33 | |
Theodore Ts'o | 80af12e | 2005-06-30 19:40:18 -0400 | [diff] [blame] | 34 | int ext2fs_set_bit(unsigned int nr,void * addr) |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 35 | { |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 36 | int mask, retval; |
| 37 | unsigned char *ADDR = (unsigned char *) addr; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 38 | |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 39 | ADDR += nr >> 3; |
| 40 | mask = 1 << (nr & 0x07); |
Theodore Ts'o | 7004b4a | 2005-02-03 21:56:44 -0500 | [diff] [blame] | 41 | retval = mask & *ADDR; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 42 | *ADDR |= mask; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 43 | return retval; |
| 44 | } |
| 45 | |
Theodore Ts'o | 80af12e | 2005-06-30 19:40:18 -0400 | [diff] [blame] | 46 | int ext2fs_clear_bit(unsigned int nr, void * addr) |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 47 | { |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 48 | int mask, retval; |
| 49 | unsigned char *ADDR = (unsigned char *) addr; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 50 | |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 51 | ADDR += nr >> 3; |
| 52 | mask = 1 << (nr & 0x07); |
Theodore Ts'o | 7004b4a | 2005-02-03 21:56:44 -0500 | [diff] [blame] | 53 | retval = mask & *ADDR; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 54 | *ADDR &= ~mask; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 55 | return retval; |
| 56 | } |
| 57 | |
Theodore Ts'o | 80af12e | 2005-06-30 19:40:18 -0400 | [diff] [blame] | 58 | int ext2fs_test_bit(unsigned int nr, const void * addr) |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 59 | { |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 60 | int mask; |
| 61 | const unsigned char *ADDR = (const unsigned char *) addr; |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 62 | |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 63 | ADDR += nr >> 3; |
| 64 | mask = 1 << (nr & 0x07); |
Theodore Ts'o | 7004b4a | 2005-02-03 21:56:44 -0500 | [diff] [blame] | 65 | return (mask & *ADDR); |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 66 | } |
Theodore Ts'o | 50e1e10 | 1997-04-26 13:58:21 +0000 | [diff] [blame] | 67 | |
Theodore Ts'o | f3db356 | 1997-04-26 13:34:30 +0000 | [diff] [blame] | 68 | #endif /* !_EXT2_HAVE_ASM_BITOPS_ */ |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 69 | |
Theodore Ts'o | f3db356 | 1997-04-26 13:34:30 +0000 | [diff] [blame] | 70 | void ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg, |
| 71 | const char *description) |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 72 | { |
Theodore Ts'o | 79a90bd | 1997-11-03 19:16:55 +0000 | [diff] [blame] | 73 | #ifndef OMIT_COM_ERR |
Theodore Ts'o | f3db356 | 1997-04-26 13:34:30 +0000 | [diff] [blame] | 74 | if (description) |
Theodore Ts'o | 5443492 | 2003-12-07 01:28:50 -0500 | [diff] [blame] | 75 | com_err(0, errcode, "#%lu for %s", arg, description); |
Theodore Ts'o | f3db356 | 1997-04-26 13:34:30 +0000 | [diff] [blame] | 76 | else |
Theodore Ts'o | 5443492 | 2003-12-07 01:28:50 -0500 | [diff] [blame] | 77 | com_err(0, errcode, "#%lu", arg); |
Theodore Ts'o | 79a90bd | 1997-11-03 19:16:55 +0000 | [diff] [blame] | 78 | #endif |
Theodore Ts'o | 3839e65 | 1997-04-26 13:21:57 +0000 | [diff] [blame] | 79 | } |
Valerie Aurora Henson | 8717c3a | 2009-06-01 16:15:40 -0400 | [diff] [blame] | 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 | |
Theodore Ts'o | c6b006e | 2012-11-24 15:58:59 -0500 | [diff] [blame] | 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 (((((unsigned long) cp) & 3) != 0) && (nbytes > 0)) { |
| 142 | res += popcount8(*cp++); |
| 143 | nbytes--; |
| 144 | } |
Theodore Ts'o | e48bf25 | 2013-05-19 18:50:10 -0400 | [diff] [blame] | 145 | p = (const __u32 *) cp; |
Theodore Ts'o | c6b006e | 2012-11-24 15:58:59 -0500 | [diff] [blame] | 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 | } |