bignum.c

/* bignum.c
 *
 * bignum operations that are missing from gmp.
 */

/* nettle, low-level cryptographics library
 *
 * Copyright (C) 2001 Niels Möller
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02111-1301, USA.
 */

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include <assert.h>
#include <string.h>

#include "bignum.h"

/* Two's complement negation means that -x = ~x + 1, ~x = -(x+1),
 * and we use that x = ~~x = ~(-x-1).
 *
 * Examples:
 *
 *   x  ~x = -x+1     ~~x = x
 *  -1          0          ff
 *  -2          1          fe
 * -7f         7e          81
 * -80         7f          80
 * -81         80        ff7f
 */

/* Including extra sign bit, if needed. Also one byte for zero. */
unsigned
nettle_mpz_sizeinbase_256_s(const mpz_t x)
{
  if (mpz_sgn(x) >= 0)
    return 1 + mpz_sizeinbase(x, 2) / 8;
  else
    {
      /* We'll output ~~x, so we need as many bits as for ~x */
      unsigned size;
      mpz_t c;

      mpz_init(c);
      mpz_com(c, x); /* Same as c = - x - 1 = |x| + 1 */
      size = 1 + mpz_sizeinbase(c,2) / 8;
      mpz_clear(c);

      return size;
    }
}

unsigned
nettle_mpz_sizeinbase_256_u(const mpz_t x)