qemu/roms/ipxe/src/arch/x86/include/bits/bigint.h

   1 #ifndef _BITS_BIGINT_H
   2 #define _BITS_BIGINT_H
   3
   4 /** @file
   5  *
   6  * Big integer support
   7  */
   8
   9 FILE_LICENCE ( GPL2_OR_LATER );
  10
  11 #include <stdint.h>
  12 #include <string.h>
  13
  14 /** Element of a big integer */
  15 typedef uint32_t bigint_element_t;
  16
  17 /**
  18  * Initialise big integer
  19  *
  20  * @v value0            Element 0 of big integer to initialise
  21  * @v size              Number of elements
  22  * @v data              Raw data
  23  * @v len               Length of raw data
  24  */
  25 static inline __attribute__ (( always_inline )) void
  26 bigint_init_raw ( uint32_t *value0, unsigned int size,
  27                   const void *data, size_t len ) {
  28         long pad_len = ( sizeof ( bigint_t ( size ) ) - len );
  29         void *discard_D;
  30         long discard_c;
  31
  32         /* Copy raw data in reverse order, padding with zeros */
  33         __asm__ __volatile__ ( "\n1:\n\t"
  34                                "movb -1(%2,%1), %%al\n\t"
  35                                "stosb\n\t"
  36                                "loop 1b\n\t"
  37                                "xorl %%eax, %%eax\n\t"
  38                                "mov %3, %1\n\t"
  39                                "rep stosb\n\t"
  40                                : "=&D" ( discard_D ), "=&c" ( discard_c )
  41                                : "r" ( data ), "g" ( pad_len ), "0" ( value0 ),
  42                                  "1" ( len )
  43                                : "eax" );
  44 }
  45
  46 /**
  47  * Add big integers
  48  *
  49  * @v addend0           Element 0 of big integer to add
  50  * @v value0            Element 0 of big integer to be added to
  51  * @v size              Number of elements
  52  */
  53 static inline __attribute__ (( always_inline )) void
  54 bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
  55                  unsigned int size ) {
  56         long index;
  57         void *discard_S;
  58         long discard_c;
  59
  60         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
  61                                "\n1:\n\t"
  62                                "lodsl\n\t"
  63                                "adcl %%eax, (%3,%0,4)\n\t"
  64                                "inc %0\n\t" /* Does not affect CF */
  65                                "loop 1b\n\t"
  66                                : "=&r" ( index ), "=&S" ( discard_S ),
  67                                  "=&c" ( discard_c )
  68                                : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
  69                                : "eax" );
  70 }
  71
  72 /**
  73  * Subtract big integers
  74  *
  75  * @v subtrahend0       Element 0 of big integer to subtract
  76  * @v value0            Element 0 of big integer to be subtracted from
  77  * @v size              Number of elements
  78  */
  79 static inline __attribute__ (( always_inline )) void
  80 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
  81                       unsigned int size ) {
  82         long index;
  83         void *discard_S;
  84         long discard_c;
  85
  86         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
  87                                "\n1:\n\t"
  88                                "lodsl\n\t"
  89                                "sbbl %%eax, (%3,%0,4)\n\t"
  90                                "inc %0\n\t" /* Does not affect CF */
  91                                "loop 1b\n\t"
  92                                : "=&r" ( index ), "=&S" ( discard_S ),
  93                                  "=&c" ( discard_c )
  94                                : "r" ( value0 ), "1" ( subtrahend0 ),
  95                                  "2" ( size )
  96                                : "eax" );
  97 }
  98
  99 /**
 100  * Rotate big integer left
 101  *
 102  * @v value0            Element 0 of big integer
 103  * @v size              Number of elements
 104  */
 105 static inline __attribute__ (( always_inline )) void
 106 bigint_rol_raw ( uint32_t *value0, unsigned int size ) {
 107         long index;
 108         long discard_c;
 109
 110         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
 111                                "\n1:\n\t"
 112                                "rcll $1, (%2,%0,4)\n\t"
 113                                "inc %0\n\t" /* Does not affect CF */
 114                                "loop 1b\n\t"
 115                                : "=&r" ( index ), "=&c" ( discard_c )
 116                                : "r" ( value0 ), "1" ( size ) );
 117 }
 118
 119 /**
 120  * Rotate big integer right
 121  *
 122  * @v value0            Element 0 of big integer
 123  * @v size              Number of elements
 124  */
 125 static inline __attribute__ (( always_inline )) void
 126 bigint_ror_raw ( uint32_t *value0, unsigned int size ) {
 127         long discard_c;
 128
 129         __asm__ __volatile__ ( "clc\n\t"
 130                                "\n1:\n\t"
 131                                "rcrl $1, -4(%1,%0,4)\n\t"
 132                                "loop 1b\n\t"
 133                                : "=&c" ( discard_c )
 134                                : "r" ( value0 ), "0" ( size ) );
 135 }
 136
 137 /**
 138  * Test if big integer is equal to zero
 139  *
 140  * @v value0            Element 0 of big integer
 141  * @v size              Number of elements
 142  * @ret is_zero         Big integer is equal to zero
 143  */
 144 static inline __attribute__ (( always_inline, pure )) int
 145 bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
 146         void *discard_D;
 147         long discard_c;
 148         int result;
 149
 150         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Set ZF */
 151                                "repe scasl\n\t"
 152                                "sete %b0\n\t"
 153                                : "=&a" ( result ), "=&D" ( discard_D ),
 154                                  "=&c" ( discard_c )
 155                                : "1" ( value0 ), "2" ( size ) );
 156         return result;
 157 }
 158
 159 /**
 160  * Compare big integers
 161  *
 162  * @v value0            Element 0 of big integer
 163  * @v reference0        Element 0 of reference big integer
 164  * @v size              Number of elements
 165  * @ret geq             Big integer is greater than or equal to the reference
 166  */
 167 static inline __attribute__ (( always_inline, pure )) int
 168 bigint_is_geq_raw ( const uint32_t *value0, const uint32_t *reference0,
 169                     unsigned int size ) {
 170         const bigint_t ( size ) __attribute__ (( may_alias )) *value =
 171                 ( ( const void * ) value0 );
 172         const bigint_t ( size ) __attribute__ (( may_alias )) *reference =
 173                 ( ( const void * ) reference0 );
 174         void *discard_S;
 175         void *discard_D;
 176         long discard_c;
 177         int result;
 178
 179         __asm__ __volatile__ ( "std\n\t"
 180                                "\n1:\n\t"
 181                                "lodsl\n\t"
 182                                "scasl\n\t"
 183                                "loope 1b\n\t"
 184                                "setae %b0\n\t"
 185                                "cld\n\t"
 186                                : "=q" ( result ), "=&S" ( discard_S ),
 187                                  "=&D" ( discard_D ), "=&c" ( discard_c )
 188                                : "0" ( 0 ), "1" ( &value->element[ size - 1 ] ),
 189                                  "2" ( &reference->element[ size - 1 ] ),
 190                                  "3" ( size )
 191                                : "eax" );
 192         return result;
 193 }
 194
 195 /**
 196  * Test if bit is set in big integer
 197  *
 198  * @v value0            Element 0 of big integer
 199  * @v size              Number of elements
 200  * @v bit               Bit to test
 201  * @ret is_set          Bit is set
 202  */
 203 static inline __attribute__ (( always_inline )) int
 204 bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
 205                         unsigned int bit ) {
 206         const bigint_t ( size ) __attribute__ (( may_alias )) *value =
 207                 ( ( const void * ) value0 );
 208         unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
 209         unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
 210
 211         return ( value->element[index] & ( 1 << subindex ) );
 212 }
 213
 214 /**
 215  * Find highest bit set in big integer
 216  *
 217  * @v value0            Element 0 of big integer
 218  * @v size              Number of elements
 219  * @ret max_bit         Highest bit set + 1 (or 0 if no bits set)
 220  */
 221 static inline __attribute__ (( always_inline )) int
 222 bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
 223         long discard_c;
 224         int result;
 225
 226         __asm__ __volatile__ ( "\n1:\n\t"
 227                                "bsrl -4(%2,%1,4), %0\n\t"
 228                                "loopz 1b\n\t"
 229                                "rol %1\n\t" /* Does not affect ZF */
 230                                "rol %1\n\t"
 231                                "leal 1(%k0,%k1,8), %k0\n\t"
 232                                "jnz 2f\n\t"
 233                                "xor %0, %0\n\t"
 234                                "\n2:\n\t"
 235                                : "=&r" ( result ), "=&c" ( discard_c )
 236                                : "r" ( value0 ), "1" ( size ) );
 237         return result;
 238 }
 239
 240 /**
 241  * Grow big integer
 242  *
 243  * @v source0           Element 0 of source big integer
 244  * @v source_size       Number of elements in source big integer
 245  * @v dest0             Element 0 of destination big integer
 246  * @v dest_size         Number of elements in destination big integer
 247  */
 248 static inline __attribute__ (( always_inline )) void
 249 bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
 250                   uint32_t *dest0, unsigned int dest_size ) {
 251         long pad_size = ( dest_size - source_size );
 252         void *discard_D;
 253         void *discard_S;
 254         long discard_c;
 255
 256         __asm__ __volatile__ ( "rep movsl\n\t"
 257                                "xorl %%eax, %%eax\n\t"
 258                                "mov %3, %2\n\t"
 259                                "rep stosl\n\t"
 260                                : "=&D" ( discard_D ), "=&S" ( discard_S ),
 261                                  "=&c" ( discard_c )
 262                                : "g" ( pad_size ), "0" ( dest0 ),
 263                                  "1" ( source0 ), "2" ( source_size )
 264                                : "eax" );
 265 }
 266
 267 /**
 268  * Shrink big integer
 269  *
 270  * @v source0           Element 0 of source big integer
 271  * @v source_size       Number of elements in source big integer
 272  * @v dest0             Element 0 of destination big integer
 273  * @v dest_size         Number of elements in destination big integer
 274  */
 275 static inline __attribute__ (( always_inline )) void
 276 bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
 277                     uint32_t *dest0, unsigned int dest_size ) {
 278         void *discard_D;
 279         void *discard_S;
 280         long discard_c;
 281
 282         __asm__ __volatile__ ( "rep movsl\n\t"
 283                                : "=&D" ( discard_D ), "=&S" ( discard_S ),
 284                                  "=&c" ( discard_c )
 285                                : "0" ( dest0 ), "1" ( source0 ),
 286                                  "2" ( dest_size )
 287                                : "eax" );
 288 }
 289
 290 /**
 291  * Finalise big integer
 292  *
 293  * @v value0            Element 0 of big integer to finalise
 294  * @v size              Number of elements
 295  * @v out               Output buffer
 296  * @v len               Length of output buffer
 297  */
 298 static inline __attribute__ (( always_inline )) void
 299 bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
 300                   void *out, size_t len ) {
 301         void *discard_D;
 302         long discard_c;
 303
 304         /* Copy raw data in reverse order */
 305         __asm__ __volatile__ ( "\n1:\n\t"
 306                                "movb -1(%2,%1), %%al\n\t"
 307                                "stosb\n\t"
 308                                "loop 1b\n\t"
 309                                : "=&D" ( discard_D ), "=&c" ( discard_c )
 310                                : "r" ( value0 ), "0" ( out ), "1" ( len )
 311                                : "eax" );
 312 }
 313
 314 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
 315                                   const uint32_t *multiplier0,
 316                                   uint32_t *value0, unsigned int size );
 317
 318 #endif /* _BITS_BIGINT_H */