13839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o/* 23839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o * bitops.c --- Bitmap frobbing code. See bitops.h for the inlined 33839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o * routines. 4efc6f628e15de95bcd13e4f0ee223cb42115d520Theodore Ts'o * 521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o. 621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o * 721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o * %Begin-Header% 8543547a52a20cb7e69d74921b2f691078fd55d83Theodore Ts'o * This file may be redistributed under the terms of the GNU Library 9543547a52a20cb7e69d74921b2f691078fd55d83Theodore Ts'o * General Public License, version 2. 1021c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o * %End-Header% 113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o */ 123839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include <stdio.h> 141d2ff46ae7533ffd038534b189f272d2a4122e4eTheodore Ts'o#if HAVE_SYS_TYPES_H 153839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include <sys/types.h> 161d2ff46ae7533ffd038534b189f272d2a4122e4eTheodore Ts'o#endif 17f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o 18b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o#include "ext2_fs.h" 193839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "ext2fs.h" 203839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 21f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o#ifndef _EXT2_HAVE_ASM_BITOPS_ 223839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 233839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o/* 243839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o * For the benefit of those who are trying to port Linux to another 253839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o * architecture, here are some C-language equivalents. You should 263839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o * recode these in the native assmebly language, if at all possible. 273839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o * 2850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o * C language equivalents written by Theodore Ts'o, 9/26/92. 2950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o * Modified by Pete A. Zaitcev 7/14/95 to be portable to big endian 3050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o * systems, as well as non-32 bit systems. 313839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o */ 323839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 3380af12e180bdea9ed391a0aee58e31cee7641709Theodore Ts'oint ext2fs_set_bit(unsigned int nr,void * addr) 343839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o{ 3550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o int mask, retval; 3650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o unsigned char *ADDR = (unsigned char *) addr; 373839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 3850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o ADDR += nr >> 3; 3950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o mask = 1 << (nr & 0x07); 407004b4af6e52ce8985e45bf37bde813df4d509ffTheodore Ts'o retval = mask & *ADDR; 413839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o *ADDR |= mask; 423839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return retval; 433839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 443839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 4580af12e180bdea9ed391a0aee58e31cee7641709Theodore Ts'oint ext2fs_clear_bit(unsigned int nr, void * addr) 463839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o{ 4750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o int mask, retval; 4850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o unsigned char *ADDR = (unsigned char *) addr; 493839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 5050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o ADDR += nr >> 3; 5150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o mask = 1 << (nr & 0x07); 527004b4af6e52ce8985e45bf37bde813df4d509ffTheodore Ts'o retval = mask & *ADDR; 533839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o *ADDR &= ~mask; 543839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return retval; 553839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 563839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 5780af12e180bdea9ed391a0aee58e31cee7641709Theodore Ts'oint ext2fs_test_bit(unsigned int nr, const void * addr) 583839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o{ 5950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o int mask; 6050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o const unsigned char *ADDR = (const unsigned char *) addr; 613839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 6250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o ADDR += nr >> 3; 6350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o mask = 1 << (nr & 0x07); 647004b4af6e52ce8985e45bf37bde813df4d509ffTheodore Ts'o return (mask & *ADDR); 653839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 6650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 67f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o#endif /* !_EXT2_HAVE_ASM_BITOPS_ */ 683839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 69f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'ovoid ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg, 70f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o const char *description) 713839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o{ 7279a90bdad033e101c38bb3c3207c8f4be47a2de7Theodore Ts'o#ifndef OMIT_COM_ERR 73f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o if (description) 74544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o com_err(0, errcode, "#%lu for %s", arg, description); 75f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o else 76544349270e4c74a6feb971123884a8cf5052a7eeTheodore Ts'o com_err(0, errcode, "#%lu", arg); 7779a90bdad033e101c38bb3c3207c8f4be47a2de7Theodore Ts'o#endif 783839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 79e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 80e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall/* 81e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall * C-only 64 bit ops. 82e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall */ 83e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 84e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallint ext2fs_set_bit64(__u64 nr, void * addr) 85e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall{ 86e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall int mask, retval; 87e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall unsigned char *ADDR = (unsigned char *) addr; 88e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 89e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall ADDR += nr >> 3; 90e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall mask = 1 << (nr & 0x07); 91e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall retval = mask & *ADDR; 92e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall *ADDR |= mask; 93e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall return retval; 94e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall} 95e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 96e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallint ext2fs_clear_bit64(__u64 nr, void * addr) 97e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall{ 98e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall int mask, retval; 99e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall unsigned char *ADDR = (unsigned char *) addr; 100e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 101e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall ADDR += nr >> 3; 102e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall mask = 1 << (nr & 0x07); 103e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall retval = mask & *ADDR; 104e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall *ADDR &= ~mask; 105e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall return retval; 106e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall} 107e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 108e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallint ext2fs_test_bit64(__u64 nr, const void * addr) 109e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall{ 110e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall int mask; 111e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall const unsigned char *ADDR = (const unsigned char *) addr; 112e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 113e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall ADDR += nr >> 3; 114e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall mask = 1 << (nr & 0x07); 115e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall return (mask & *ADDR); 116e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall} 117e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 118e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallstatic unsigned int popcount8(unsigned int w) 119e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall{ 120e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall unsigned int res = w - ((w >> 1) & 0x55); 121e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res = (res & 0x33) + ((res >> 2) & 0x33); 122e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall return (res + (res >> 4)) & 0x0F; 123e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall} 124e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 125e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallstatic unsigned int popcount32(unsigned int w) 126e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall{ 127e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall unsigned int res = w - ((w >> 1) & 0x55555555); 128e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res = (res & 0x33333333) + ((res >> 2) & 0x33333333); 129e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res = (res + (res >> 4)) & 0x0F0F0F0F; 130e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res = res + (res >> 8); 131e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall return (res + (res >> 16)) & 0x000000FF; 132e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall} 133e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 134e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrallunsigned int ext2fs_bitcount(const void *addr, unsigned int nbytes) 135e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall{ 136e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall const unsigned char *cp = addr; 137e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall const __u32 *p; 138e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall unsigned int res = 0; 139e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 140e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall while (((((unsigned long) cp) & 3) != 0) && (nbytes > 0)) { 141e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res += popcount8(*cp++); 142e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall nbytes--; 143e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall } 144e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall p = (const __u32 *) cp; 145e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 146e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall while (nbytes > 4) { 147e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res += popcount32(*p++); 148e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall nbytes -= 4; 149e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall } 150e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall cp = (const unsigned char *) p; 151e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall 152e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall while (nbytes > 0) { 153e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall res += popcount8(*cp++); 154e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall nbytes--; 155e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall } 156e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall return res; 157e0ed7404719a9ddd2ba427a80db5365c8bad18c0JP Abgrall} 158