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

   1 /*
   2  * This file is part of DisOrder.
   3  * Copyright (C) 2005, 2007, 2008 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 "common.h"
  28
  29 #include "basen.h"
  30
  31 /** @brief Test whether v is 0
  32  * @param v Pointer to bigendian bignum
  33  * @param nwords Length of bignum
  34  * @return !v
  35  */
  36 static int zero(const unsigned long *v, int nwords) {
  37   int n;
  38
  39   for(n = 0; n < nwords && !v[n]; ++n)
  40     ;
  41   return n == nwords;
  42 }
  43
  44 /** @brief Divide v by m returning the remainder.
  45  * @param v Pointer to bigendian bignum
  46  * @param nwords Length of bignum
  47  * @param m Divisor (must not be 0)
  48  * @return Remainder
  49  *
  50  * The quotient is stored in @p v.
  51  */
  52 static unsigned divide(unsigned long *v, int nwords, unsigned long m) {
  53   unsigned long r = 0, a, b;
  54   int n;
  55
  56   /* we do the divide 16 bits at a time */
  57   for(n = 0; n < nwords; ++n) {
  58     a = v[n] >> 16;
  59     b = v[n] & 0xFFFF;
  60     a += r << 16;
  61     r = a % m;
  62     a /= m;
  63     b += r << 16;
  64     r = b % m;
  65     b /= m;
  66     v[n] = (a << 16) + b;
  67   }
  68   return r;
  69 }
  70
  71 /** @brief Convert v to a chosen base
  72  * @param v Pointer to bigendian bignum (modified!)
  73  * @param nwords Length of bignum
  74  * @param buffer Output buffer
  75  * @param bufsize Size of output buffer
  76  * @param base Number base (2..62)
  77  * @return 0 on success, -1 if the buffer is too small
  78  *
  79  * Converts @p v to a string in the given base using decimal digits, lower case
  80  * letter sand upper case letters as digits.
  81  */
  82 int basen(unsigned long *v,
  83           int nwords,
  84           char buffer[],
  85           size_t bufsize,
  86           unsigned base) {
  87   size_t i = bufsize;
  88   static const char chars[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  89
  90   do {
  91     if(i <= 1)
  92       return -1;                        /* overflow */
  93     buffer[--i] = chars[divide(v, nwords, base)];
  94   } while(!zero(v, nwords));
  95   memmove(buffer, buffer + i, bufsize - i);
  96   buffer[bufsize - i] = 0;
  97   return 0;
  98 }
  99
 100 /*
 101 Local Variables:
 102 c-basic-offset:2
 103 comment-column:40
 104 fill-column:79
 105 End:
 106 */