qemu/roms/ipxe/src/arch/x86/core/x86_bigint.c

   1 /*
   2  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 #include <stdint.h>
  27 #include <string.h>
  28 #include <ipxe/bigint.h>
  29
  30 /** @file
  31  *
  32  * Big integer support
  33  */
  34
  35 /**
  36  * Multiply big integers
  37  *
  38  * @v multiplicand0     Element 0 of big integer to be multiplied
  39  * @v multiplier0       Element 0 of big integer to be multiplied
  40  * @v result0           Element 0 of big integer to hold result
  41  * @v size              Number of elements
  42  */
  43 void bigint_multiply_raw ( const uint32_t *multiplicand0,
  44                            const uint32_t *multiplier0,
  45                            uint32_t *result0, unsigned int size ) {
  46         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
  47                 ( ( const void * ) multiplicand0 );
  48         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
  49                 ( ( const void * ) multiplier0 );
  50         bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
  51                 ( ( void * ) result0 );
  52         unsigned int i;
  53         unsigned int j;
  54         uint32_t multiplicand_element;
  55         uint32_t multiplier_element;
  56         uint32_t *result_elements;
  57         uint32_t discard_a;
  58         uint32_t discard_d;
  59         long index;
  60
  61         /* Zero result */
  62         memset ( result, 0, sizeof ( *result ) );
  63
  64         /* Multiply integers one element at a time */
  65         for ( i = 0 ; i < size ; i++ ) {
  66                 multiplicand_element = multiplicand->element[i];
  67                 for ( j = 0 ; j < size ; j++ ) {
  68                         multiplier_element = multiplier->element[j];
  69                         result_elements = &result->element[ i + j ];
  70                         /* Perform a single multiply, and add the
  71                          * resulting double-element into the result,
  72                          * carrying as necessary.  The carry can
  73                          * never overflow beyond the end of the
  74                          * result, since:
  75                          *
  76                          *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
  77                          */
  78                         __asm__ __volatile__ ( "mull %4\n\t"
  79                                                "addl %%eax, (%5,%2,4)\n\t"
  80                                                "adcl %%edx, 4(%5,%2,4)\n\t"
  81                                                "\n1:\n\t"
  82                                                "adcl $0, 8(%5,%2,4)\n\t"
  83                                                "inc %2\n\t"
  84                                                        /* Does not affect CF */
  85                                                "jc 1b\n\t"
  86                                                : "=&a" ( discard_a ),
  87                                                  "=&d" ( discard_d ),
  88                                                  "=&r" ( index )
  89                                                : "0" ( multiplicand_element ),
  90                                                  "g" ( multiplier_element ),
  91                                                  "r" ( result_elements ),
  92                                                  "2" ( 0 ) );
  93                 }
  94         }
  95 }