Line data    Source code

       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    23796250 :         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      636114 :         BUG_ON(v == 0); /* division by zero */
      39             : 
      40      636114 :         return gfinv[v];
      41             : }
      42             : 
      43             : /*
      44             :  * GF 2^a.
      45             :  */
      46             : static __always_inline uint8_t pow2(int v)
      47             : {
      48         396 :         BUG_ON(v < 0 || v > 254); /* invalid exponent */
      49             : 
      50         396 :         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      409825 :         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     2605672 :         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    35788608 :         uint32_t mask = v & 0x80808080U;
      90             : 
      91    35788608 :         mask = (mask << 1) - (mask >> 7);
      92    35788608 :         v = (v << 1) & 0xfefefefeU;
      93    35788608 :         v ^= mask & 0x1d1d1d1dU;
      94    35788608 :         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    34409376 :         uint64_t mask = v & 0x8080808080808080ULL;
     103             : 
     104    34409376 :         mask = (mask << 1) - (mask >> 7);
     105    34409376 :         v = (v << 1) & 0xfefefefefefefefeULL;
     106    34409376 :         v ^= mask & 0x1d1d1d1d1d1d1d1dULL;
     107    34409376 :         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    13764544 :         uint32_t mask = v & 0x01010101U;
     116             : 
     117    13764544 :         mask = (mask << 8) - mask;
     118    13764544 :         v = (v >> 1) & 0x7f7f7f7fU;
     119    13764544 :         v ^= mask & 0x8e8e8e8eU;
     120    13764544 :         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    13304800 :         uint64_t mask = v & 0x0101010101010101ULL;
     129             : 
     130    13304800 :         mask = (mask << 8) - mask;
     131    13304800 :         v = (v >> 1) & 0x7f7f7f7f7f7f7f7fULL;
     132    13304800 :         v ^= mask & 0x8e8e8e8e8e8e8e8eULL;
     133    13304800 :         return v;
     134             : }
     135             : 
     136             : #endif
     137             :