chiark - git - mdw - disorder/blob - lib/basen.c

   1 /*
   2  * This file is part of DisOrder.
   3  * Copyright (C) 2005 Richard Kettlewell
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  18  * USA
  19  */
  20 /** @file lib/basen.c @brief Arbitrary base conversion
  21  *
  22  * The functions in this file handle arbitrary-size non-negative integers,
  23  * represented as a bigendian (MSW first) sequence of @c unsigned @c long
  24  * words.  The words themselves use the native byte order.
  25  */
  26
  27 #include <config.h>
  28 #include "types.h"
  29
  30 #include <string.h>
  31
  32 #include "basen.h"
  33
  34 /** @brief Test whether v is 0
  35  * @param v Pointer to bigendian bignum
  36  * @param nwords Length of bignum
  37  * @return !v
  38  */
  39 static int zero(const unsigned long *v, int nwords) {
  40   int n;
  41
  42   for(n = 0; n < nwords && !v[n]; ++n)
  43     ;
  44   return n == nwords;
  45 }
  46
  47 /** @brief Divide v by m returning the remainder.
  48  * @param v Pointer to bigendian bignum
  49  * @param nwords Length of bignum
  50  * @param m Divisor (must not be 0)
  51  * @return Remainder
  52  *
  53  * The quotient is stored in @p v.
  54  */
  55 static unsigned divide(unsigned long *v, int nwords, unsigned long m) {
  56   unsigned long r = 0, a, b;
  57   int n;
  58
  59   /* we do the divide 16 bits at a time */
  60   for(n = 0; n < nwords; ++n) {
  61     a = v[n] >> 16;
  62     b = v[n] & 0xFFFF;
  63     a += r << 16;
  64     r = a % m;
  65     a /= m;
  66     b += r << 16;
  67     r = b % m;
  68     b /= m;
  69     v[n] = (a << 16) + b;
  70   }
  71   return r;
  72 }
  73
  74 /** @brief Convert v to a chosen base
  75  * @param v Pointer to bigendian bignum (modified!)
  76  * @param nwords Length of bignum
  77  * @param buffer Output buffer
  78  * @param bufsize Size of output buffer
  79  * @param base Number base (2..62)
  80  * @return 0 on success, -1 if the buffer is too small
  81  *
  82  * Converts @p v to a string in the given base using decimal digits, lower case
  83  * letter sand upper case letters as digits.
  84  */
  85 int basen(unsigned long *v,
  86           int nwords,
  87           char buffer[],
  88           size_t bufsize,
  89           unsigned base) {
  90   size_t i = bufsize;
  91   static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  92
  93   do {
  94     if(i <= 1)
  95       return -1;                        /* overflow */
  96     buffer[--i] = chars[divide(v, nwords, base)];
  97   } while(!zero(v, nwords));
  98   memmove(buffer, buffer + i, bufsize - i);
  99   buffer[bufsize - i] = 0;
 100   return 0;
 101 }
 102
 103 /*
 104 Local Variables:
 105 c-basic-offset:2
 106 comment-column:40
 107 fill-column:79
 108 End:
 109 */