fs/reiser4/dscale.c

   1 /* Copyright 2001, 2002, 2003 by Hans Reiser, licensing governed by
   2  * reiser4/README */
   3
   4 /* Scalable on-disk integers */
   5
   6 /*
   7  * Various on-disk structures contain integer-like structures. Stat-data
   8  * contain [yes, "data" is plural, check the dictionary] file size, link
   9  * count; extent unit contains extent width etc. To accommodate for general
  10  * case enough space is reserved to keep largest possible value. 64 bits in
  11  * all cases above. But in overwhelming majority of cases numbers actually
  12  * stored in these fields will be comparatively small and reserving 8 bytes is
  13  * a waste of precious disk bandwidth.
  14  *
  15  * Scalable integers are one way to solve this problem. dscale_write()
  16  * function stores __u64 value in the given area consuming from 1 to 9 bytes,
  17  * depending on the magnitude of the value supplied. dscale_read() reads value
  18  * previously stored by dscale_write().
  19  *
  20  * dscale_write() produces format not completely unlike of UTF: two highest
  21  * bits of the first byte are used to store "tag". One of 4 possible tag
  22  * values is chosen depending on the number being encoded:
  23  *
  24  *           0 ... 0x3f               => 0           [table 1]
  25  *        0x40 ... 0x3fff             => 1
  26  *      0x4000 ... 0x3fffffff         => 2
  27  *  0x40000000 ... 0xffffffffffffffff => 3
  28  *
  29  * (see dscale_range() function)
  30  *
  31  * Values in the range 0x40000000 ... 0xffffffffffffffff require 8 full bytes
  32  * to be stored, so in this case there is no place in the first byte to store
  33  * tag. For such values tag is stored in an extra 9th byte.
  34  *
  35  * As _highest_ bits are used for the test (which is natural) scaled integers
  36  * are stored in BIG-ENDIAN format in contrast with the rest of reiser4 which
  37  * uses LITTLE-ENDIAN.
  38  *
  39  */
  40
  41 #include "debug.h"
  42 #include "dscale.h"
  43
  44 /* return tag of scaled integer stored at @address */
  45 static int gettag(const unsigned char *address)
  46 {
  47         /* tag is stored in two highest bits */
  48         return (*address) >> 6;
  49 }
  50
  51 /* clear tag from value. Clear tag embedded into @value. */
  52 static void cleartag(__u64 *value, int tag)
  53 {
  54         /*
  55          * W-w-what ?!
  56          *
  57          * Actually, this is rather simple: @value passed here was read by
  58          * dscale_read(), converted from BIG-ENDIAN, and padded to __u64 by
  59          * zeroes. Tag is still stored in the highest (arithmetically)
  60          * non-zero bits of @value, but relative position of tag within __u64
  61          * depends on @tag.
  62          *
  63          * For example if @tag is 0, it's stored 2 highest bits of lowest
  64          * byte, and its offset (counting from lowest bit) is 8 - 2 == 6 bits.
  65          *
  66          * If tag is 1, it's stored in two highest bits of 2nd lowest byte,
  67          * and it's offset if (2 * 8) - 2 == 14 bits.
  68          *
  69          * See table 1 above for details.
  70          *
  71          * All these cases are captured by the formula:
  72          */
  73         *value &= ~(3 << (((1 << tag) << 3) - 2));
  74         /*
  75          * That is, clear two (3 == 0t11) bits at the offset
  76          *
  77          *                  8 * (2 ^ tag) - 2,
  78          *
  79          * that is, two highest bits of (2 ^ tag)-th byte of @value.
  80          */
  81 }
  82
  83 /* return tag for @value. See table 1 above for details. */
  84 static int dscale_range(__u64 value)
  85 {
  86         if (value > 0x3fffffff)
  87                 return 3;
  88         if (value > 0x3fff)
  89                 return 2;
  90         if (value > 0x3f)
  91                 return 1;
  92         return 0;
  93 }
  94
  95 /* restore value stored at @adderss by dscale_write() and return number of
  96  * bytes consumed */
  97 int dscale_read(unsigned char *address, __u64 *value)
  98 {
  99         int tag;
 100
 101         /* read tag */
 102         tag = gettag(address);
 103         switch (tag) {
 104         case 3:
 105                 /* In this case tag is stored in an extra byte, skip this byte
 106                  * and decode value stored in the next 8 bytes.*/
 107                 *value = __be64_to_cpu(get_unaligned((__be64 *)(address + 1)));
 108                 /* worst case: 8 bytes for value itself plus one byte for
 109                  * tag. */
 110                 return 9;
 111         case 0:
 112                 *value = get_unaligned(address);
 113                 break;
 114         case 1:
 115                 *value = __be16_to_cpu(get_unaligned((__be16 *)address));
 116                 break;
 117         case 2:
 118                 *value = __be32_to_cpu(get_unaligned((__be32 *)address));
 119                 break;
 120         default:
 121                 return RETERR(-EIO);
 122         }
 123         /* clear tag embedded into @value */
 124         cleartag(value, tag);
 125         /* number of bytes consumed is (2 ^ tag)---see table 1. */
 126         return 1 << tag;
 127 }
 128
 129 /* number of bytes consumed */
 130 int dscale_bytes_to_read(unsigned char *address)
 131 {
 132         int tag;
 133
 134         tag = gettag(address);
 135         switch (tag) {
 136         case 0:
 137         case 1:
 138         case 2:
 139                 return 1 << tag;
 140         case 3:
 141                 return 9;
 142         default:
 143                 return RETERR(-EIO);
 144         }
 145 }
 146
 147 /* store @value at @address and return number of bytes consumed */
 148 int dscale_write(unsigned char *address, __u64 value)
 149 {
 150         int tag;
 151         int shift;
 152         __be64 v;
 153         unsigned char *valarr;
 154
 155         tag = dscale_range(value);
 156         v = __cpu_to_be64(value);
 157         valarr = (unsigned char *)&v;
 158         shift = (tag == 3) ? 1 : 0;
 159         memcpy(address + shift, valarr + sizeof v - (1 << tag), 1 << tag);
 160         *address |= (tag << 6);
 161         return shift + (1 << tag);
 162 }
 163
 164 /* number of bytes required to store @value */
 165 int dscale_bytes_to_write(__u64 value)
 166 {
 167         int bytes;
 168
 169         bytes = 1 << dscale_range(value);
 170         if (bytes == 8)
 171                 ++bytes;
 172         return bytes;
 173 }
 174
 175 /* returns true if @value and @other require the same number of bytes to be
 176  * stored. Used by detect when data structure (like stat-data) has to be
 177  * expanded or contracted. */
 178 int dscale_fit(__u64 value, __u64 other)
 179 {
 180         return dscale_range(value) == dscale_range(other);
 181 }
 182
 183 /* Make Linus happy.
 184    Local variables:
 185    c-indentation-style: "K&R"
 186    mode-name: "LC"
 187    c-basic-offset: 8
 188    tab-width: 8
 189    fill-column: 120
 190    scroll-step: 1
 191    End:
 192 */