git.distorted.org.uk Git - u/mdw/catacomb/blob - gfx.h

   1 /* -*-c-*-
   2  *
   3  * $Id: gfx.h,v 1.1 2000/10/08 15:49:37 mdw Exp $
   4  *
   5  * Low-level arithmetic on binary polynomials
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: gfx.h,v $
  33  * Revision 1.1  2000/10/08 15:49:37  mdw
  34  * First glimmerings of binary polynomial arithmetic.
  35  *
  36  */
  37
  38 #ifndef CATACOMB_GFX_H
  39 #define CATACOMB_GFX_H
  40
  41 #ifdef __cplusplus
  42   extern "C" {
  43 #endif
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #ifndef CATACOMB_MPX_H
  48 #  include "mpx.h"
  49 #endif
  50
  51 /*----- Functions provided ------------------------------------------------*/
  52
  53 /* --- @gfx_add@ --- *
  54  *
  55  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  56  *              @const mpw *av, *avl@ = first addend vector base and limit
  57  *              @const mpw *bv, *bvl@ = second addend vector base and limit
  58  *
  59  * Returns:     ---
  60  *
  61  * Use:         Adds two %$\gf{2}$% polynomials.  This is the same as
  62  *              subtraction.
  63  */
  64
  65 extern void gfx_add(mpw */*dv*/, mpw */*dvl*/,
  66                     const mpw */*av*/, const mpw */*avl*/,
  67                     const mpw */*bv*/, const mpw */*bvl*/);
  68
  69 /* --- @gfx_acc@ --- *
  70  *
  71  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  72  *              @const mpw *av, *avl@ = addend vector base and limit
  73  *
  74  * Returns:     ---
  75  *
  76  * Use:         Adds the addend into the destination.  This is considerably
  77  *              faster than the three-address add call.
  78  */
  79
  80 extern void gfx_acc(mpw */*dv*/, mpw */*dvl*/,
  81                     const mpw */*av*/, const mpw */*avl*/);
  82
  83 /* --- @gfx_accshift@ --- *
  84  *
  85  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
  86  *              @const mpw *av, *avl@ = addend vector base and limit
  87  *              @size_t n@ = number of bits to shift
  88  *
  89  * Returns:     ---
  90  *
  91  * Use:         Shifts the argument left by %$n$% places and adds it to the
  92  *              destination.  This is a primitive used by multiplication and
  93  *              division.
  94  */
  95
  96 extern void gfx_accshift(mpw */*dv*/, mpw */*dvl*/,
  97                          const mpw */*av*/, const mpw */*avl*/,
  98                          size_t /*n*/);
  99
 100 /* --- @gfx_mul@ --- *
 101  *
 102  * Arguments:   @mpw *dv, *dvl@ = destination vector base and limit
 103  *              @const mpw *av, *avl@ = first argument vector base and limit
 104  *              @const mpw *bv, *bvl@ = second argument vector base and limit
 105  *
 106  * Returns:     ---
 107  *
 108  * Use:         Does multiplication of polynomials over %$\gf{2}$%.
 109  */
 110
 111 extern void gfx_mul(mpw */*dv*/, mpw */*dvl*/,
 112                     const mpw */*av*/, const mpw */*avl*/,
 113                     const mpw */*bv*/, const mpw */*bvl*/);
 114
 115 /* --- @gfx_div@ --- *
 116  *
 117  * Arguments:   @mpw *qv, *qvl@ = quotient vector base and limit
 118  *              @mpw *rv, *rvl@ = dividend/remainder vector base and limit
 119  *              @const mpw *dv, *dvl@ = divisor vector base and limit
 120  *
 121  * Returns:     ---
 122  *
 123  * Use:         Performs division on polynomials over %$\gf{2}$%.
 124  */
 125
 126 extern void gfx_div(mpw */*qv*/, mpw */*qvl*/, mpw */*rv*/, mpw */*rvl*/,
 127                     const mpw */*dv*/, const mpw */*dvl*/);
 128
 129 /*----- Karatsuba multiplication algorithms -------------------------------*/
 130
 131 /* --- @GFK_THRESH@ --- *
 132  *
 133  * This is the limiting length for using Karatsuba algorithms.  It's best to
 134  * use the simpler classical multiplication method on numbers smaller than
 135  * this.
 136  */
 137
 138 #define GFK_THRESH 2
 139
 140 /* --- @gfx_kmul@ --- *
 141  *
 142  * Arguments:   @mpw *dv, *dvl@ = pointer to destination buffer
 143  *              @const mpw *av, *avl@ = pointer to first argument
 144  *              @const mpw *bv, *bvl@ = pointer to second argument
 145  *              @mpw *sv, *svl@ = pointer to scratch workspace
 146  *
 147  * Returns:     ---
 148  *
 149  * Use:         Multiplies two binary polynomials using Karatsuba's
 150  *              algorithm.  This is rather faster than traditional long
 151  *              multiplication (e.g., @gfx_umul@) on polynomials with large
 152  *              degree, although more expensive on small ones.
 153  *
 154  *              The destination must be twice as large as the larger
 155  *              argument.  The scratch space must be twice as large as the
 156  *              larger argument.
 157  */
 158
 159 extern void gfx_kmul(mpw */*dv*/, mpw */*dvl*/,
 160                      const mpw */*av*/, const mpw */*avl*/,
 161                      const mpw */*bv*/, const mpw */*bvl*/,
 162                      mpw */*sv*/, mpw */*svl*/);
 163
 164 /*----- That's all, folks -------------------------------------------------*/
 165
 166 #ifdef __cplusplus
 167   }
 168 #endif
 169
 170 #endif