fs/ntfs3/bitfunc.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  *
   4  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
   5  *
   6  */
   7
   8 #include <linux/types.h>
   9
  10 #include "ntfs_fs.h"
  11
  12 #define BITS_IN_SIZE_T (sizeof(size_t) * 8)
  13
  14 /*
  15  * fill_mask[i] - first i bits are '1' , i = 0,1,2,3,4,5,6,7,8
  16  * fill_mask[i] = 0xFF >> (8-i)
  17  */
  18 static const u8 fill_mask[] = { 0x00, 0x01, 0x03, 0x07, 0x0F,
  19                                 0x1F, 0x3F, 0x7F, 0xFF };
  20
  21 /*
  22  * zero_mask[i] - first i bits are '0' , i = 0,1,2,3,4,5,6,7,8
  23  * zero_mask[i] = 0xFF << i
  24  */
  25 static const u8 zero_mask[] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xF0,
  26                                 0xE0, 0xC0, 0x80, 0x00 };
  27
  28 /*
  29  * are_bits_clear
  30  *
  31  * Return: True if all bits [bit, bit+nbits) are zeros "0".
  32  */
  33 bool are_bits_clear(const void *lmap, size_t bit, size_t nbits)
  34 {
  35         size_t pos = bit & 7;
  36         const u8 *map = (u8 *)lmap + (bit >> 3);
  37
  38         if (pos) {
  39                 if (8 - pos >= nbits)
  40                         return !nbits || !(*map & fill_mask[pos + nbits] &
  41                                            zero_mask[pos]);
  42
  43                 if (*map++ & zero_mask[pos])
  44                         return false;
  45                 nbits -= 8 - pos;
  46         }
  47
  48         pos = ((size_t)map) & (sizeof(size_t) - 1);
  49         if (pos) {
  50                 pos = sizeof(size_t) - pos;
  51                 if (nbits >= pos * 8) {
  52                         for (nbits -= pos * 8; pos; pos--, map++) {
  53                                 if (*map)
  54                                         return false;
  55                         }
  56                 }
  57         }
  58
  59         for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) {
  60                 if (*((size_t *)map))
  61                         return false;
  62         }
  63
  64         for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) {
  65                 if (*map)
  66                         return false;
  67         }
  68
  69         pos = nbits & 7;
  70         if (pos && (*map & fill_mask[pos]))
  71                 return false;
  72
  73         return true;
  74 }
  75
  76 /*
  77  * are_bits_set
  78  *
  79  * Return: True if all bits [bit, bit+nbits) are ones "1".
  80  */
  81 bool are_bits_set(const void *lmap, size_t bit, size_t nbits)
  82 {
  83         u8 mask;
  84         size_t pos = bit & 7;
  85         const u8 *map = (u8 *)lmap + (bit >> 3);
  86
  87         if (pos) {
  88                 if (8 - pos >= nbits) {
  89                         mask = fill_mask[pos + nbits] & zero_mask[pos];
  90                         return !nbits || (*map & mask) == mask;
  91                 }
  92
  93                 mask = zero_mask[pos];
  94                 if ((*map++ & mask) != mask)
  95                         return false;
  96                 nbits -= 8 - pos;
  97         }
  98
  99         pos = ((size_t)map) & (sizeof(size_t) - 1);
 100         if (pos) {
 101                 pos = sizeof(size_t) - pos;
 102                 if (nbits >= pos * 8) {
 103                         for (nbits -= pos * 8; pos; pos--, map++) {
 104                                 if (*map != 0xFF)
 105                                         return false;
 106                         }
 107                 }
 108         }
 109
 110         for (pos = nbits / BITS_IN_SIZE_T; pos; pos--, map += sizeof(size_t)) {
 111                 if (*((size_t *)map) != MINUS_ONE_T)
 112                         return false;
 113         }
 114
 115         for (pos = (nbits % BITS_IN_SIZE_T) >> 3; pos; pos--, map++) {
 116                 if (*map != 0xFF)
 117                         return false;
 118         }
 119
 120         pos = nbits & 7;
 121         if (pos) {
 122                 mask = fill_mask[pos];
 123                 if ((*map & mask) != mask)
 124                         return false;
 125         }
 126
 127         return true;
 128 }