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