chiark - git - mdw - catacomb/blob - math/scaf.h

   1 /* -*-c-*-
   2  *
   3  * Simple scalar fields
   4  *
   5  * (c) 2017 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 #ifndef CATACOMB_SCAF_H
  29 #define CATACOMB_SCAF_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #include <mLib/bits.h>
  38
  39 /*----- Type selection ----------------------------------------------------*/
  40
  41 #ifndef SCAF_IMPL
  42 #  ifdef HAVE_UINT64
  43 #    define SCAF_IMPL 32
  44 #  else
  45 #    define SCAF_IMPL 16
  46 #  endif
  47 #endif
  48
  49 #if SCAF_IMPL == 32
  50   typedef uint32 scaf_piece;
  51   typedef uint64 scaf_dblpiece;
  52 #endif
  53 #if SCAF_IMPL == 16
  54   typedef uint16 scaf_piece;
  55   typedef uint32 scaf_dblpiece;
  56 #endif
  57
  58 #define SCAF_NPIECE(bits, piecewd) (((bits) + piecewd - 1)/piecewd)
  59
  60 /*----- Functions provided -----------------------------------------------*/
  61
  62 /* --- @scaf_load@ --- *
  63  *
  64  * Arguments:   @scaf_piece *z@ = where to write the result
  65  *              @const octet *b@ = source buffer to read
  66  *              @size_t sz@ = size of the source buffer
  67  *              @size_t npiece@ = number of pieces to read
  68  *              @unsigned piecewd@ = nominal width of pieces in bits
  69  *
  70  * Returns:     ---
  71  *
  72  * Use:         Loads a little-endian encoded scalar into a vector @z@ of
  73  *              single-precision pieces.
  74  */
  75
  76 extern void scaf_load(scaf_piece */*z*/, const octet */*b*/, size_t /*sz*/,
  77                       size_t /*npiece*/, unsigned /*piecewd*/);
  78
  79 /* --- @scaf_loaddbl@ --- *
  80  *
  81  * Arguments:   @scaf_dblpiece *z@ = where to write the result
  82  *              @const octet *b@ = source buffer to read
  83  *              @size_t sz@ = size of the source buffer
  84  *              @size_t npiece@ = number of pieces to read
  85  *              @unsigned piecewd@ = nominal width of pieces in bits
  86  *
  87  * Returns:     ---
  88  *
  89  * Use:         Loads a little-endian encoded scalar into a vector @z@ of
  90  *              double-precision pieces.
  91  */
  92
  93 extern void scaf_loaddbl(scaf_dblpiece */*z*/, const octet */*b*/,
  94                          size_t /*sz*/, size_t /*npiece*/,
  95                          unsigned /*piecewd*/);
  96
  97 /* --- @scaf_store@ --- *
  98  *
  99  * Arguments:   @octet *b@ = buffer to fill in
 100  *              @size_t sz@ = size of the buffer
 101  *              @const scaf_piece *x@ = scalar to store
 102  *              @size_t npiece@ = number of pieces in @x@
 103  *              @unsigned piecewd@ = nominal width of pieces in bits
 104  *
 105  * Returns:     ---
 106  *
 107  * Use:         Stores a scalar in a vector of single-precison pieces as a
 108  *              little-endian vector of bytes.
 109  */
 110
 111 extern void scaf_store(octet */*b*/, size_t /*sz*/, const scaf_piece */*x*/,
 112                        size_t /*npiece*/, unsigned /*piecewd*/);
 113
 114 /* --- @scaf_mul@ --- *
 115  *
 116  * Arguments:   @scaf_dblpiece *z@ = where to put the answer
 117  *              @const scaf_piece *x, *y@ = the operands
 118  *              @size_t npiece@ = the length of the operands
 119  *
 120  * Returns:     ---
 121  *
 122  * Use:         Multiply two scalars.  The destination must have space for
 123  *              @2*npiece@ pieces (though the last one will always be zero).
 124  *              The result is not reduced.
 125  */
 126
 127 extern void scaf_mul(scaf_dblpiece */*z*/, const scaf_piece */*x*/,
 128                      const scaf_piece */*y*/, size_t /*npiece*/);
 129
 130 /* --- @scaf_reduce@ --- *
 131  *
 132  * Arguments:   @scaf_piece *z@ = where to write the result
 133  *              @const scaf_dblpiece *x@ = the operand to reduce
 134  *              @const scaf_piece *l@ = the modulus, in internal format
 135  *              @const scaf_piece *mu@ = scaled approximation to @1/l@
 136  *              @size_t npiece@ = number of pieces in @l@
 137  *              @unsigned piecewd@ = nominal width of a piece in bits
 138  *              @scaf_piece *scratch@ = @3*npiece@ scratch pieces
 139  *
 140  * Returns:     ---
 141  *
 142  * Use:         Reduce @x@ (a vector of @2*npiece@ double-precision pieces)
 143  *              modulo @l@ (a vector of @npiece@ single-precision pieces),
 144  *              writing the result to @z@.
 145  *
 146  *              Write @n = npiece@, @w = piecewd@, and %$B = 2^w$%.  The
 147  *              operand @mu@ must contain %$\lfloor B^{2n}/l \rfloor$%, in
 148  *              @npiece + 1@ pieces.  Furthermore, we must have
 149  *              %$3 l < B^n$%.  (Fiddle with %$w$% if necessary.)
 150  */
 151
 152 extern void scaf_reduce(scaf_piece */*z*/, const scaf_dblpiece */*x*/,
 153                         const scaf_piece */*l*/, const scaf_piece */*mu*/,
 154                         size_t /*npiece*/, unsigned /*piecewd*/,
 155                         scaf_piece */*scratch*/);
 156
 157 /*----- That's all, folks -------------------------------------------------*/
 158
 159 #ifdef __cplusplus
 160   }
 161 #endif
 162
 163 #endif