iPXE
bigint.h
Go to the documentation of this file.
00001 #ifndef _BITS_BIGINT_H
00002 #define _BITS_BIGINT_H
00003 
00004 /** @file
00005  *
00006  * Big integer support
00007  */
00008 
00009 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00010 
00011 #include <stdint.h>
00012 #include <string.h>
00013 
00014 /** Element of a big integer */
00015 typedef uint32_t bigint_element_t;
00016 
00017 /**
00018  * Initialise big integer
00019  *
00020  * @v value0            Element 0 of big integer to initialise
00021  * @v size              Number of elements
00022  * @v data              Raw data
00023  * @v len               Length of raw data
00024  */
00025 static inline __attribute__ (( always_inline )) void
00026 bigint_init_raw ( uint32_t *value0, unsigned int size,
00027                   const void *data, size_t len ) {
00028         long pad_len = ( sizeof ( bigint_t ( size ) ) - len );
00029         void *discard_D;
00030         long discard_c;
00031 
00032         /* Copy raw data in reverse order, padding with zeros */
00033         __asm__ __volatile__ ( "\n1:\n\t"
00034                                "movb -1(%2,%1), %%al\n\t"
00035                                "stosb\n\t"
00036                                "loop 1b\n\t"
00037                                "xorl %%eax, %%eax\n\t"
00038                                "mov %3, %1\n\t"
00039                                "rep stosb\n\t"
00040                                : "=&D" ( discard_D ), "=&c" ( discard_c )
00041                                : "r" ( data ), "g" ( pad_len ), "0" ( value0 ),
00042                                  "1" ( len )
00043                                : "eax" );
00044 }
00045 
00046 /**
00047  * Add big integers
00048  *
00049  * @v addend0           Element 0 of big integer to add
00050  * @v value0            Element 0 of big integer to be added to
00051  * @v size              Number of elements
00052  */
00053 static inline __attribute__ (( always_inline )) void
00054 bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
00055                  unsigned int size ) {
00056         long index;
00057         void *discard_S;
00058         long discard_c;
00059 
00060         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
00061                                "\n1:\n\t"
00062                                "lodsl\n\t"
00063                                "adcl %%eax, (%3,%0,4)\n\t"
00064                                "inc %0\n\t" /* Does not affect CF */
00065                                "loop 1b\n\t"
00066                                : "=&r" ( index ), "=&S" ( discard_S ),
00067                                  "=&c" ( discard_c )
00068                                : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
00069                                : "eax" );
00070 }
00071 
00072 /**
00073  * Subtract big integers
00074  *
00075  * @v subtrahend0       Element 0 of big integer to subtract
00076  * @v value0            Element 0 of big integer to be subtracted from
00077  * @v size              Number of elements
00078  */
00079 static inline __attribute__ (( always_inline )) void
00080 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
00081                       unsigned int size ) {
00082         long index;
00083         void *discard_S;
00084         long discard_c;
00085 
00086         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
00087                                "\n1:\n\t"
00088                                "lodsl\n\t"
00089                                "sbbl %%eax, (%3,%0,4)\n\t"
00090                                "inc %0\n\t" /* Does not affect CF */
00091                                "loop 1b\n\t"
00092                                : "=&r" ( index ), "=&S" ( discard_S ),
00093                                  "=&c" ( discard_c )
00094                                : "r" ( value0 ), "1" ( subtrahend0 ),
00095                                  "2" ( size )
00096                                : "eax" );
00097 }
00098 
00099 /**
00100  * Rotate big integer left
00101  *
00102  * @v value0            Element 0 of big integer
00103  * @v size              Number of elements
00104  */
00105 static inline __attribute__ (( always_inline )) void
00106 bigint_rol_raw ( uint32_t *value0, unsigned int size ) {
00107         long index;
00108         long discard_c;
00109 
00110         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
00111                                "\n1:\n\t"
00112                                "rcll $1, (%2,%0,4)\n\t"
00113                                "inc %0\n\t" /* Does not affect CF */
00114                                "loop 1b\n\t"
00115                                : "=&r" ( index ), "=&c" ( discard_c )
00116                                : "r" ( value0 ), "1" ( size ) );
00117 }
00118 
00119 /**
00120  * Rotate big integer right
00121  *
00122  * @v value0            Element 0 of big integer
00123  * @v size              Number of elements
00124  */
00125 static inline __attribute__ (( always_inline )) void
00126 bigint_ror_raw ( uint32_t *value0, unsigned int size ) {
00127         long discard_c;
00128 
00129         __asm__ __volatile__ ( "clc\n\t"
00130                                "\n1:\n\t"
00131                                "rcrl $1, -4(%1,%0,4)\n\t"
00132                                "loop 1b\n\t"
00133                                : "=&c" ( discard_c )
00134                                : "r" ( value0 ), "0" ( size ) );
00135 }
00136 
00137 /**
00138  * Test if big integer is equal to zero
00139  *
00140  * @v value0            Element 0 of big integer
00141  * @v size              Number of elements
00142  * @ret is_zero         Big integer is equal to zero
00143  */
00144 static inline __attribute__ (( always_inline, pure )) int
00145 bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
00146         void *discard_D;
00147         long discard_c;
00148         int result;
00149 
00150         __asm__ __volatile__ ( "xor %0, %0\n\t" /* Set ZF */
00151                                "repe scasl\n\t"
00152                                "sete %b0\n\t"
00153                                : "=&a" ( result ), "=&D" ( discard_D ),
00154                                  "=&c" ( discard_c )
00155                                : "1" ( value0 ), "2" ( size ) );
00156         return result;
00157 }
00158 
00159 /**
00160  * Compare big integers
00161  *
00162  * @v value0            Element 0 of big integer
00163  * @v reference0        Element 0 of reference big integer
00164  * @v size              Number of elements
00165  * @ret geq             Big integer is greater than or equal to the reference
00166  */
00167 static inline __attribute__ (( always_inline, pure )) int
00168 bigint_is_geq_raw ( const uint32_t *value0, const uint32_t *reference0,
00169                     unsigned int size ) {
00170         const bigint_t ( size ) __attribute__ (( may_alias )) *value =
00171                 ( ( const void * ) value0 );
00172         const bigint_t ( size ) __attribute__ (( may_alias )) *reference =
00173                 ( ( const void * ) reference0 );
00174         void *discard_S;
00175         void *discard_D;
00176         long discard_c;
00177         int result;
00178 
00179         __asm__ __volatile__ ( "std\n\t"
00180                                "\n1:\n\t"
00181                                "lodsl\n\t"
00182                                "scasl\n\t"
00183                                "loope 1b\n\t"
00184                                "setae %b0\n\t"
00185                                "cld\n\t"
00186                                : "=q" ( result ), "=&S" ( discard_S ),
00187                                  "=&D" ( discard_D ), "=&c" ( discard_c )
00188                                : "0" ( 0 ), "1" ( &value->element[ size - 1 ] ),
00189                                  "2" ( &reference->element[ size - 1 ] ),
00190                                  "3" ( size )
00191                                : "eax" );
00192         return result;
00193 }
00194 
00195 /**
00196  * Test if bit is set in big integer
00197  *
00198  * @v value0            Element 0 of big integer
00199  * @v size              Number of elements
00200  * @v bit               Bit to test
00201  * @ret is_set          Bit is set
00202  */
00203 static inline __attribute__ (( always_inline )) int
00204 bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
00205                         unsigned int bit ) {
00206         const bigint_t ( size ) __attribute__ (( may_alias )) *value =
00207                 ( ( const void * ) value0 );
00208         unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
00209         unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
00210 
00211         return ( value->element[index] & ( 1 << subindex ) );
00212 }
00213 
00214 /**
00215  * Find highest bit set in big integer
00216  *
00217  * @v value0            Element 0 of big integer
00218  * @v size              Number of elements
00219  * @ret max_bit         Highest bit set + 1 (or 0 if no bits set)
00220  */
00221 static inline __attribute__ (( always_inline )) int
00222 bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
00223         long discard_c;
00224         int result;
00225 
00226         __asm__ __volatile__ ( "\n1:\n\t"
00227                                "bsrl -4(%2,%1,4), %0\n\t"
00228                                "loopz 1b\n\t"
00229                                "rol %1\n\t" /* Does not affect ZF */
00230                                "rol %1\n\t"
00231                                "leal 1(%k0,%k1,8), %k0\n\t"
00232                                "jnz 2f\n\t"
00233                                "xor %0, %0\n\t"
00234                                "\n2:\n\t"
00235                                : "=&r" ( result ), "=&c" ( discard_c )
00236                                : "r" ( value0 ), "1" ( size ) );
00237         return result;
00238 }
00239 
00240 /**
00241  * Grow big integer
00242  *
00243  * @v source0           Element 0 of source big integer
00244  * @v source_size       Number of elements in source big integer
00245  * @v dest0             Element 0 of destination big integer
00246  * @v dest_size         Number of elements in destination big integer
00247  */
00248 static inline __attribute__ (( always_inline )) void
00249 bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
00250                   uint32_t *dest0, unsigned int dest_size ) {
00251         long pad_size = ( dest_size - source_size );
00252         void *discard_D;
00253         void *discard_S;
00254         long discard_c;
00255 
00256         __asm__ __volatile__ ( "rep movsl\n\t"
00257                                "xorl %%eax, %%eax\n\t"
00258                                "mov %3, %2\n\t"
00259                                "rep stosl\n\t"
00260                                : "=&D" ( discard_D ), "=&S" ( discard_S ),
00261                                  "=&c" ( discard_c )
00262                                : "g" ( pad_size ), "0" ( dest0 ),
00263                                  "1" ( source0 ), "2" ( source_size )
00264                                : "eax" );
00265 }
00266 
00267 /**
00268  * Shrink big integer
00269  *
00270  * @v source0           Element 0 of source big integer
00271  * @v source_size       Number of elements in source big integer
00272  * @v dest0             Element 0 of destination big integer
00273  * @v dest_size         Number of elements in destination big integer
00274  */
00275 static inline __attribute__ (( always_inline )) void
00276 bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
00277                     uint32_t *dest0, unsigned int dest_size ) {
00278         void *discard_D;
00279         void *discard_S;
00280         long discard_c;
00281 
00282         __asm__ __volatile__ ( "rep movsl\n\t"
00283                                : "=&D" ( discard_D ), "=&S" ( discard_S ),
00284                                  "=&c" ( discard_c )
00285                                : "0" ( dest0 ), "1" ( source0 ),
00286                                  "2" ( dest_size )
00287                                : "eax" );
00288 }
00289 
00290 /**
00291  * Finalise big integer
00292  *
00293  * @v value0            Element 0 of big integer to finalise
00294  * @v size              Number of elements
00295  * @v out               Output buffer
00296  * @v len               Length of output buffer
00297  */
00298 static inline __attribute__ (( always_inline )) void
00299 bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
00300                   void *out, size_t len ) {
00301         void *discard_D;
00302         long discard_c;
00303 
00304         /* Copy raw data in reverse order */
00305         __asm__ __volatile__ ( "\n1:\n\t"
00306                                "movb -1(%2,%1), %%al\n\t"
00307                                "stosb\n\t"
00308                                "loop 1b\n\t"
00309                                : "=&D" ( discard_D ), "=&c" ( discard_c )
00310                                : "r" ( value0 ), "0" ( out ), "1" ( len )
00311                                : "eax" );
00312 }
00313 
00314 extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
00315                                   const uint32_t *multiplier0,
00316                                   uint32_t *value0, unsigned int size );
00317 
00318 #endif /* _BITS_BIGINT_H */