1 /* $OpenBSD: math_2n.h,v 1.8 2005/04/21 01:23:07 cloder Exp $ */ 2 /* $EOM: math_2n.h,v 1.9 1999/04/17 23:20:32 niklas Exp $ */ 3 4 /* 5 * Copyright (c) 1998 Niels Provos. All rights reserved. 6 * Copyright (c) 1999 Niklas Hallqvist. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 /* 30 * This code was written under funding by Ericsson Radio Systems. 31 */ 32 33 #ifndef _MATH_2N_H 34 #define _MATH_2N_H_ 35 36 /* 37 * The chunk size we use is variable, this allows speed ups 38 * for processors like the Alpha with 64bit words. 39 * XXX - b2n_mask is only up to 32 bit at the moment. 40 */ 41 42 #define USE_32BIT /* XXX - This obviously needs fixing */ 43 44 #ifdef USE_32BIT 45 #define CHUNK_TYPE u_int32_t 46 #define CHUNK_BITS 32 47 #define CHUNK_SHIFTS 5 48 #define CHUNK_BMASK 0xffffffff 49 #define CHUNK_MASK (CHUNK_BITS - 1) 50 #define CHUNK_BYTES (CHUNK_BITS >> 3) 51 #define CHUNK_NIBBLES (CHUNK_BITS >> 2) 52 #else 53 #define CHUNK_TYPE u_int8_t 54 #define CHUNK_BITS 8 55 #define CHUNK_SHIFTS 3 56 #define CHUNK_BMASK 0xff 57 #define CHUNK_MASK (CHUNK_BITS - 1) 58 #define CHUNK_BYTES (CHUNK_BITS >> 3) 59 #define CHUNK_NIBBLES (CHUNK_BITS >> 2) 60 #endif 61 62 extern CHUNK_TYPE b2n_mask[CHUNK_BITS]; 63 64 /* An element of GF(2**n), n = bits */ 65 66 typedef struct { 67 u_int16_t chunks; 68 u_int16_t bits; 69 u_int8_t dirty; /* Sig bits are dirty */ 70 CHUNK_TYPE *limp; 71 } _b2n; 72 73 typedef _b2n *b2n_ptr; 74 typedef _b2n b2n_t[1]; 75 76 #define B2N_SET(x,y) do \ 77 { \ 78 (x)->chunks = (y)->chunks; \ 79 (x)->bits = (y)->bits; \ 80 (x)->limp = (y)->limp; \ 81 (x)->dirty = (y)->dirty; \ 82 } \ 83 while (0) 84 85 #define B2N_SWAP(x,y) do \ 86 { \ 87 b2n_t _t_; \ 88 \ 89 B2N_SET (_t_, (x)); \ 90 B2N_SET ((x), (y)); \ 91 B2N_SET ((y), _t_); \ 92 } \ 93 while (0) 94 95 #define B2N_MIN(x,y) ((x)->chunks > (y)->chunks ? (y) : (x)) 96 #define B2N_MAX(x,y) ((x)->chunks > (y)->chunks ? (x) : (y)) 97 98 int b2n_3mul(b2n_ptr, b2n_ptr); 99 int b2n_add(b2n_ptr, b2n_ptr, b2n_ptr); 100 int b2n_cmp(b2n_ptr, b2n_ptr); 101 int b2n_cmp_null(b2n_ptr); 102 int b2n_div(b2n_ptr, b2n_ptr, b2n_ptr, b2n_ptr); 103 int b2n_div_mod(b2n_ptr, b2n_ptr, b2n_ptr, b2n_ptr); 104 int b2n_div_q(b2n_ptr, b2n_ptr, b2n_ptr); 105 int b2n_div_r(b2n_ptr, b2n_ptr, b2n_ptr); 106 int b2n_exp_mod(b2n_ptr, b2n_ptr, u_int32_t, b2n_ptr); 107 void b2n_init(b2n_ptr); 108 void b2n_clear(b2n_ptr); 109 int b2n_gcd(b2n_ptr, b2n_ptr, b2n_ptr); 110 int b2n_halftrace(b2n_ptr, b2n_ptr, b2n_ptr); 111 int b2n_lshift(b2n_ptr, b2n_ptr, unsigned int); 112 int b2n_mod(b2n_ptr, b2n_ptr, b2n_ptr); 113 int b2n_mul(b2n_ptr, b2n_ptr, b2n_ptr); 114 int b2n_mul_inv(b2n_ptr, b2n_ptr, b2n_ptr); 115 int b2n_nadd(b2n_ptr, b2n_ptr, b2n_ptr); 116 int b2n_nsub(b2n_ptr, b2n_ptr, b2n_ptr); 117 int b2n_random(b2n_ptr, u_int32_t); 118 int b2n_resize(b2n_ptr, unsigned int); 119 int b2n_rshift(b2n_ptr, b2n_ptr, unsigned int); 120 int b2n_set(b2n_ptr, b2n_ptr); 121 int b2n_set_null(b2n_ptr); 122 int b2n_set_str(b2n_ptr, char *); 123 int b2n_set_ui(b2n_ptr, unsigned int); 124 u_int32_t b2n_sigbit(b2n_ptr); 125 int b2n_sqrt(b2n_ptr, b2n_ptr, b2n_ptr); 126 int b2n_square(b2n_ptr, b2n_ptr); 127 #define b2n_sub b2n_add 128 int b2n_trace(b2n_ptr, b2n_ptr, b2n_ptr); 129 130 #endif /* _MATH_2N_H_ */ 131