bitops.c revision e48bf256e99e4923c6193ff78000af18c700d93d
16f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 26f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * bitops.c --- Bitmap frobbing code. See bitops.h for the inlined 36f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * routines. 46f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 56f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o. 66f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 76f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * %Begin-Header% 86f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * This file may be redistributed under the terms of the GNU Library 96f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * General Public License, version 2. 106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * %End-Header% 116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "config.h" 146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include <stdio.h> 156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#if HAVE_SYS_TYPES_H 166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include <sys/types.h> 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#endif 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "ext2_fs.h" 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "ext2fs.h" 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#ifndef _EXT2_HAVE_ASM_BITOPS_ 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * For the benefit of those who are trying to port Linux to another 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * architecture, here are some C-language equivalents. You should 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * recode these in the native assmebly language, if at all possible. 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * C language equivalents written by Theodore Ts'o, 9/26/92. 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Modified by Pete A. Zaitcev 7/14/95 to be portable to big endian 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * systems, as well as non-32 bit systems. 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint ext2fs_set_bit(unsigned int nr,void * addr) 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int mask, retval; 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned char *ADDR = (unsigned char *) addr; 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ADDR += nr >> 3; 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mask = 1 << (nr & 0x07); 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org retval = mask & *ADDR; 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *ADDR |= mask; 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return retval; 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint ext2fs_clear_bit(unsigned int nr, void * addr) 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int mask, retval; 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned char *ADDR = (unsigned char *) addr; 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ADDR += nr >> 3; 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mask = 1 << (nr & 0x07); 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org retval = mask & *ADDR; 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *ADDR &= ~mask; 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return retval; 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint ext2fs_test_bit(unsigned int nr, const void * addr) 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int mask; 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const unsigned char *ADDR = (const unsigned char *) addr; 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ADDR += nr >> 3; 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mask = 1 << (nr & 0x07); 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (mask & *ADDR); 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#endif /* !_EXT2_HAVE_ASM_BITOPS_ */ 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgvoid ext2fs_warn_bitmap(errcode_t errcode, unsigned long arg, 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const char *description) 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#ifndef OMIT_COM_ERR 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if (description) 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org com_err(0, errcode, "#%lu for %s", arg, description); 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org else 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org com_err(0, errcode, "#%lu", arg); 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#endif 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * C-only 64 bit ops. 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint ext2fs_set_bit64(__u64 nr, void * addr) 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int mask, retval; 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned char *ADDR = (unsigned char *) addr; 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ADDR += nr >> 3; 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mask = 1 << (nr & 0x07); 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org retval = mask & *ADDR; 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *ADDR |= mask; 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return retval; 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint ext2fs_clear_bit64(__u64 nr, void * addr) 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int mask, retval; 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned char *ADDR = (unsigned char *) addr; 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ADDR += nr >> 3; 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mask = 1 << (nr & 0x07); 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org retval = mask & *ADDR; 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *ADDR &= ~mask; 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return retval; 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgint ext2fs_test_bit64(__u64 nr, const void * addr) 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int mask; 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const unsigned char *ADDR = (const unsigned char *) addr; 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ADDR += nr >> 3; 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org mask = 1 << (nr & 0x07); 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (mask & *ADDR); 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic unsigned int popcount8(unsigned int w) 1206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 1216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned int res = w - ((w >> 1) & 0x55); 1226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res = (res & 0x33) + ((res >> 2) & 0x33); 1236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (res + (res >> 4)) & 0x0F; 1246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic unsigned int popcount32(unsigned int w) 1276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 1286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned int res = w - ((w >> 1) & 0x55555555); 1296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res = (res & 0x33333333) + ((res >> 2) & 0x33333333); 1306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res = (res + (res >> 4)) & 0x0F0F0F0F; 1316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res = res + (res >> 8); 1326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (res + (res >> 16)) & 0x000000FF; 1336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgunsigned int ext2fs_bitcount(const void *addr, unsigned int nbytes) 1366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org{ 1376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const unsigned char *cp = addr; 1386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org const __u32 *p; 1396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org unsigned int res = 0; 1406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (((((unsigned long) cp) & 3) != 0) && (nbytes > 0)) { 1426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res += popcount8(*cp++); 1436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org nbytes--; 1446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p = (const __u32 *) cp; 1466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (nbytes > 4) { 1486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res += popcount32(*p++); 1496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org nbytes -= 4; 1506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org cp = (const unsigned char *) p; 1526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while (nbytes > 0) { 1546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org res += popcount8(*cp++); 1556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org nbytes--; 1566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return res; 1586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org