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

   1 /* -*-c-*-
   2  *
   3  * Low-level arithmetic on binary polynomials
   4  *
   5  * (c) 2000 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_GFX_H
  29 #define CATACOMB_GFX_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #ifndef CATACOMB_MPX_H
  38 #  include "mpx.h"
  39 #endif
  40
  41 /*----- Functions provided ------------------------------------------------*/
  42
  43 /* --- @gfx_add@ --- *
  44  *
  45  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  46  *              @const mpw *av, *avl@ = first addend vector base and limit
  47  *              @const mpw *bv, *bvl@ = second addend vector base and limit
  48  *
  49  * Returns:     ---
  50  *
  51  * Use:         Adds two %$\gf{2}$% polynomials.  This is the same as
  52  *              subtraction.
  53  */
  54
  55 extern void gfx_add(mpw */*dv*/, mpw */*dvl*/,
  56                     const mpw */*av*/, const mpw */*avl*/,
  57                     const mpw */*bv*/, const mpw */*bvl*/);
  58
  59 /* --- @gfx_acc@ --- *
  60  *
  61  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  62  *              @const mpw *av, *avl@ = addend vector base and limit
  63  *
  64  * Returns:     ---
  65  *
  66  * Use:         Adds the addend into the destination.  This is considerably
  67  *              faster than the three-address add call.
  68  */
  69
  70 extern void gfx_acc(mpw */*dv*/, mpw */*dvl*/,
  71                     const mpw */*av*/, const mpw */*avl*/);
  72
  73 /* --- @gfx_accshift@ --- *
  74  *
  75  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  76  *              @const mpw *av, *avl@ = addend vector base and limit
  77  *              @size_t n@ = number of bits to shift
  78  *
  79  * Returns:     ---
  80  *
  81  * Use:         Shifts the argument left by %$n$% places and adds it to the
  82  *              destination.  This is a primitive used by multiplication and
  83  *              division.
  84  */
  85
  86 extern void gfx_accshift(mpw */*dv*/, mpw */*dvl*/,
  87                          const mpw */*av*/, const mpw */*avl*/,
  88                          size_t /*n*/);
  89
  90 /* --- @gfx_mul@ --- *
  91  *
  92  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  93  *              @const mpw *av, *avl@ = first argument vector base and limit
  94  *              @const mpw *bv, *bvl@ = second argument vector base and limit
  95  *
  96  * Returns:     ---
  97  *
  98  * Use:         Does multiplication of polynomials over %$\gf{2}$%.
  99  */
 100
 101 extern void gfx_mul(mpw */*dv*/, mpw */*dvl*/,
 102                     const mpw */*av*/, const mpw */*avl*/,
 103                     const mpw */*bv*/, const mpw */*bvl*/);
 104
 105 /* --- @gfx_sqr@ --- *
 106  *
 107  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
 108  *              @const mpw *av, *avl@ = argument vector base and limit
 109  *
 110  * Returns:     ---
 111  *
 112  * Use:         Performs squaring of binary polynomials.
 113  */
 114
 115 extern void gfx_sqr(mpw */*dv*/, mpw */*dvl*/,
 116                     const mpw */*av*/, const mpw */*avl*/);
 117
 118 /* --- @gfx_div@ --- *
 119  *
 120  * Arguments:   @mpw *qv, *qvl@ = quotient vector base and limit
 121  *              @mpw *rv, *rvl@ = dividend/remainder vector base and limit
 122  *              @const mpw *dv, *dvl@ = divisor vector base and limit
 123  *
 124  * Returns:     ---
 125  *
 126  * Use:         Performs division on polynomials over %$\gf{2}$%.
 127  */
 128
 129 extern void gfx_div(mpw */*qv*/, mpw */*qvl*/, mpw */*rv*/, mpw */*rvl*/,
 130                     const mpw */*dv*/, const mpw */*dvl*/);
 131
 132 /*----- Karatsuba multiplication algorithms -------------------------------*/
 133
 134 /* --- @GFK_THRESH@ --- *
 135  *
 136  * This is the limiting length for using Karatsuba algorithms.  It's best to
 137  * use the simpler classical multiplication method on numbers smaller than
 138  * this.
 139  */
 140
 141 #define GFK_THRESH 2
 142
 143 /* --- @gfx_kmul@ --- *
 144  *
 145  * Arguments:   @mpw *dv, *dvl@ = pointer to destination buffer
 146  *              @const mpw *av, *avl@ = pointer to first argument
 147  *              @const mpw *bv, *bvl@ = pointer to second argument
 148  *              @mpw *sv, *svl@ = pointer to scratch workspace
 149  *
 150  * Returns:     ---
 151  *
 152  * Use:         Multiplies two binary polynomials using Karatsuba's
 153  *              algorithm.  This is rather faster than traditional long
 154  *              multiplication (e.g., @gfx_umul@) on polynomials with large
 155  *              degree, although more expensive on small ones.
 156  *
 157  *              The destination must be twice as large as the larger
 158  *              argument.  The scratch space must be twice as large as the
 159  *              larger argument.
 160  */
 161
 162 extern void gfx_kmul(mpw */*dv*/, mpw */*dvl*/,
 163                      const mpw */*av*/, const mpw */*avl*/,
 164                      const mpw */*bv*/, const mpw */*bvl*/,
 165                      mpw */*sv*/, mpw */*svl*/);
 166
 167 /*----- That's all, folks -------------------------------------------------*/
 168
 169 #ifdef __cplusplus
 170   }
 171 #endif
 172
 173 #endif