git.sesse.net Git - bcachefs-tools-debian/blob - raid/gf.h

   1 /*
   2  * Copyright (C) 2013 Andrea Mazzoleni
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  */
  14
  15 #ifndef __RAID_GF_H
  16 #define __RAID_GF_H
  17
  18 /*
  19  * Galois field operations.
  20  *
  21  * Basic range checks are implemented using BUG_ON().
  22  */
  23
  24 /*
  25  * GF a*b.
  26  */
  27 static __always_inline uint8_t mul(uint8_t a, uint8_t b)
  28 {
  29         return gfmul[a][b];
  30 }
  31
  32 /*
  33  * GF 1/a.
  34  * Not defined for a == 0.
  35  */
  36 static __always_inline uint8_t inv(uint8_t v)
  37 {
  38         BUG_ON(v == 0); /* division by zero */
  39
  40         return gfinv[v];
  41 }
  42
  43 /*
  44  * GF 2^a.
  45  */
  46 static __always_inline uint8_t pow2(int v)
  47 {
  48         BUG_ON(v < 0 || v > 254); /* invalid exponent */
  49
  50         return gfexp[v];
  51 }
  52
  53 /*
  54  * Gets the multiplication table for a specified value.
  55  */
  56 static __always_inline const uint8_t *table(uint8_t v)
  57 {
  58         return gfmul[v];
  59 }
  60
  61 /*
  62  * Gets the generator matrix coefficient for parity 'p' and disk 'd'.
  63  */
  64 static __always_inline uint8_t A(int p, int d)
  65 {
  66         return gfgen[p][d];
  67 }
  68
  69 /*
  70  * Dereference as uint8_t
  71  */
  72 #define v_8(p) (*(uint8_t *)&(p))
  73
  74 /*
  75  * Dereference as uint32_t
  76  */
  77 #define v_32(p) (*(uint32_t *)&(p))
  78
  79 /*
  80  * Dereference as uint64_t
  81  */
  82 #define v_64(p) (*(uint64_t *)&(p))
  83
  84 /*
  85  * Multiply each byte of a uint32 by 2 in the GF(2^8).
  86  */
  87 static __always_inline uint32_t x2_32(uint32_t v)
  88 {
  89         uint32_t mask = v & 0x80808080U;
  90
  91         mask = (mask << 1) - (mask >> 7);
  92         v = (v << 1) & 0xfefefefeU;
  93         v ^= mask & 0x1d1d1d1dU;
  94         return v;
  95 }
  96
  97 /*
  98  * Multiply each byte of a uint64 by 2 in the GF(2^8).
  99  */
 100 static __always_inline uint64_t x2_64(uint64_t v)
 101 {
 102         uint64_t mask = v & 0x8080808080808080ULL;
 103
 104         mask = (mask << 1) - (mask >> 7);
 105         v = (v << 1) & 0xfefefefefefefefeULL;
 106         v ^= mask & 0x1d1d1d1d1d1d1d1dULL;
 107         return v;
 108 }
 109
 110 /*
 111  * Divide each byte of a uint32 by 2 in the GF(2^8).
 112  */
 113 static __always_inline uint32_t d2_32(uint32_t v)
 114 {
 115         uint32_t mask = v & 0x01010101U;
 116
 117         mask = (mask << 8) - mask;
 118         v = (v >> 1) & 0x7f7f7f7fU;
 119         v ^= mask & 0x8e8e8e8eU;
 120         return v;
 121 }
 122
 123 /*
 124  * Divide each byte of a uint64 by 2 in the GF(2^8).
 125  */
 126 static __always_inline uint64_t d2_64(uint64_t v)
 127 {
 128         uint64_t mask = v & 0x0101010101010101ULL;
 129
 130         mask = (mask << 8) - mask;
 131         v = (v >> 1) & 0x7f7f7f7f7f7f7f7fULL;
 132         v ^= mask & 0x8e8e8e8e8e8e8e8eULL;
 133         return v;
 134 }
 135
 136 #endif
 137