iPXE
x86_bigint.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 #include <stdint.h>
00027 #include <string.h>
00028 #include <ipxe/bigint.h>
00029 
00030 /** @file
00031  *
00032  * Big integer support
00033  */
00034 
00035 /**
00036  * Multiply big integers
00037  *
00038  * @v multiplicand0     Element 0 of big integer to be multiplied
00039  * @v multiplier0       Element 0 of big integer to be multiplied
00040  * @v result0           Element 0 of big integer to hold result
00041  * @v size              Number of elements
00042  */
00043 void bigint_multiply_raw ( const uint32_t *multiplicand0,
00044                            const uint32_t *multiplier0,
00045                            uint32_t *result0, unsigned int size ) {
00046         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
00047                 ( ( const void * ) multiplicand0 );
00048         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
00049                 ( ( const void * ) multiplier0 );
00050         bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
00051                 ( ( void * ) result0 );
00052         unsigned int i;
00053         unsigned int j;
00054         uint32_t multiplicand_element;
00055         uint32_t multiplier_element;
00056         uint32_t *result_elements;
00057         uint32_t discard_a;
00058         uint32_t discard_d;
00059         long index;
00060 
00061         /* Zero result */
00062         memset ( result, 0, sizeof ( *result ) );
00063 
00064         /* Multiply integers one element at a time */
00065         for ( i = 0 ; i < size ; i++ ) {
00066                 multiplicand_element = multiplicand->element[i];
00067                 for ( j = 0 ; j < size ; j++ ) {
00068                         multiplier_element = multiplier->element[j];
00069                         result_elements = &result->element[ i + j ];
00070                         /* Perform a single multiply, and add the
00071                          * resulting double-element into the result,
00072                          * carrying as necessary.  The carry can
00073                          * never overflow beyond the end of the
00074                          * result, since:
00075                          *
00076                          *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
00077                          */
00078                         __asm__ __volatile__ ( "mull %4\n\t"
00079                                                "addl %%eax, (%5,%2,4)\n\t"
00080                                                "adcl %%edx, 4(%5,%2,4)\n\t"
00081                                                "\n1:\n\t"
00082                                                "adcl $0, 8(%5,%2,4)\n\t"
00083                                                "inc %2\n\t"
00084                                                        /* Does not affect CF */
00085                                                "jc 1b\n\t"
00086                                                : "=&a" ( discard_a ),
00087                                                  "=&d" ( discard_d ),
00088                                                  "=&r" ( index )
00089                                                : "0" ( multiplicand_element ),
00090                                                  "g" ( multiplier_element ),
00091                                                  "r" ( result_elements ),
00092                                                  "2" ( 0 ) );
00093                 }
00094         }
00095 }