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
  20 FILE_LICENCE ( GPL2_OR_LATER );
  21
  22 #include <stdint.h>
  23 #include <string.h>
  24 #include <ipxe/bigint.h>
  25
  26 /** @file
  27  *
  28  * Big integer support
  29  */
  30
  31 /**
  32  * Multiply big integers
  33  *
  34  * @v multiplicand0     Element 0 of big integer to be multiplied
  35  * @v multiplier0       Element 0 of big integer to be multiplied
  36  * @v result0           Element 0 of big integer to hold result
  37  * @v size              Number of elements
  38  */
  39 void bigint_multiply_raw ( const uint32_t *multiplicand0,
  40                            const uint32_t *multiplier0,
  41                            uint32_t *result0, unsigned int size ) {
  42         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
  43                 ( ( const void * ) multiplicand0 );
  44         const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
  45                 ( ( const void * ) multiplier0 );
  46         bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
  47                 ( ( void * ) result0 );
  48         unsigned int i;
  49         unsigned int j;
  50         uint32_t multiplicand_element;
  51         uint32_t multiplier_element;
  52         uint32_t *result_elements;
  53         uint32_t discard_a;
  54         uint32_t discard_d;
  55         long index;
  56
  57         /* Zero result */
  58         memset ( result, 0, sizeof ( *result ) );
  59
  60         /* Multiply integers one element at a time */
  61         for ( i = 0 ; i < size ; i++ ) {
  62                 multiplicand_element = multiplicand->element[i];
  63                 for ( j = 0 ; j < size ; j++ ) {
  64                         multiplier_element = multiplier->element[j];
  65                         result_elements = &result->element[ i + j ];
  66                         /* Perform a single multiply, and add the
  67                          * resulting double-element into the result,
  68                          * carrying as necessary.  The carry can
  69                          * never overflow beyond the end of the
  70                          * result, since:
  71                          *
  72                          *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
  73                          */
  74                         __asm__ __volatile__ ( "mull %4\n\t"
  75                                                "addl %%eax, (%5,%2,4)\n\t"
  76                                                "adcl %%edx, 4(%5,%2,4)\n\t"
  77                                                "\n1:\n\t"
  78                                                "adcl $0, 8(%5,%2,4)\n\t"
  79                                                "inc %2\n\t"
  80                                                        /* Does not affect CF */
  81                                                "jc 1b\n\t"
  82                                                : "=&a" ( discard_a ),
  83                                                  "=&d" ( discard_d ),
  84                                                  "=&r" ( index )
  85                                                : "0" ( multiplicand_element ),
  86                                                  "g" ( multiplier_element ),
  87                                                  "r" ( result_elements ),
  88                                                  "2" ( 0 ) );
  89                 }
  90         }
  91 }