rts/gmp/mpn/x86/k7/diveby3.asm

   1 dnl  AMD K7 mpn_divexact_by3 -- mpn division by 3, expecting no remainder.
   2 dnl
   3 dnl  K7: 8.0 cycles/limb
   4
   5
   6 dnl  Copyright (C) 2000 Free Software Foundation, Inc.
   7 dnl
   8 dnl  This file is part of the GNU MP Library.
   9 dnl
  10 dnl  The GNU MP Library is free software; you can redistribute it and/or
  11 dnl  modify it under the terms of the GNU Lesser General Public License as
  12 dnl  published by the Free Software Foundation; either version 2.1 of the
  13 dnl  License, or (at your option) any later version.
  14 dnl
  15 dnl  The GNU MP Library is distributed in the hope that it will be useful,
  16 dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18 dnl  Lesser General Public License for more details.
  19 dnl
  20 dnl  You should have received a copy of the GNU Lesser General Public
  21 dnl  License along with the GNU MP Library; see the file COPYING.LIB.  If
  22 dnl  not, write to the Free Software Foundation, Inc., 59 Temple Place -
  23 dnl  Suite 330, Boston, MA 02111-1307, USA.
  24
  25
  26 include(`../config.m4')
  27
  28
  29 C mp_limb_t mpn_divexact_by3c (mp_ptr dst, mp_srcptr src, mp_size_t size,
  30 C                              mp_limb_t carry);
  31
  32 defframe(PARAM_CARRY,16)
  33 defframe(PARAM_SIZE, 12)
  34 defframe(PARAM_SRC,   8)
  35 defframe(PARAM_DST,   4)
  36
  37 dnl  multiplicative inverse of 3, modulo 2^32
  38 deflit(INVERSE_3,        0xAAAAAAAB)
  39
  40 dnl  ceil(b/3) and floor(b*2/3) where b=2^32
  41 deflit(ONE_THIRD_CEIL,   0x55555556)
  42 deflit(TWO_THIRDS_FLOOR, 0xAAAAAAAA)
  43
  44         .text
  45         ALIGN(32)
  46
  47 PROLOGUE(mpn_divexact_by3c)
  48 deflit(`FRAME',0)
  49
  50         movl    PARAM_SRC, %ecx
  51         pushl   %ebx                    defframe_pushl(SAVE_EBX)
  52
  53         movl    PARAM_CARRY, %ebx
  54         pushl   %ebp                    defframe_pushl(SAVE_EBP)
  55
  56         movl    PARAM_SIZE, %ebp
  57         pushl   %edi                    defframe_pushl(SAVE_EDI)
  58
  59         movl    (%ecx), %eax            C src low limb
  60         pushl   %esi                    defframe_pushl(SAVE_ESI)
  61
  62         movl    PARAM_DST, %edi
  63         movl    $TWO_THIRDS_FLOOR, %esi
  64         leal    -4(%ecx,%ebp,4), %ecx   C &src[size-1]
  65
  66         subl    %ebx, %eax
  67
  68         setc    %bl
  69         decl    %ebp
  70         jz      L(last)
  71
  72         leal    (%edi,%ebp,4), %edi     C &dst[size-1]
  73         negl    %ebp
  74
  75
  76         ALIGN(16)
  77 L(top):
  78         C eax   src limb, carry subtracted
  79         C ebx   carry limb (0 or 1)
  80         C ecx   &src[size-1]
  81         C edx   scratch
  82         C esi   TWO_THIRDS_FLOOR
  83         C edi   &dst[size-1]
  84         C ebp   counter, limbs, negative
  85
  86         imull   $INVERSE_3, %eax, %edx
  87
  88         movl    4(%ecx,%ebp,4), %eax    C next src limb
  89         cmpl    $ONE_THIRD_CEIL, %edx
  90
  91         sbbl    $-1, %ebx               C +1 if result>=ceil(b/3)
  92         cmpl    %edx, %esi
  93
  94         sbbl    %ebx, %eax              C and further 1 if result>=ceil(b*2/3)
  95         movl    %edx, (%edi,%ebp,4)
  96         incl    %ebp
  97
  98         setc    %bl                     C new carry
  99         jnz     L(top)
 100
 101
 102
 103 L(last):
 104         C eax   src limb, carry subtracted
 105         C ebx   carry limb (0 or 1)
 106         C ecx   &src[size-1]
 107         C edx   scratch
 108         C esi   multiplier
 109         C edi   &dst[size-1]
 110         C ebp
 111
 112         imull   $INVERSE_3, %eax
 113
 114         cmpl    $ONE_THIRD_CEIL, %eax
 115         movl    %eax, (%edi)
 116         movl    SAVE_EBP, %ebp
 117
 118         sbbl    $-1, %ebx               C +1 if eax>=ceil(b/3)
 119         cmpl    %eax, %esi
 120         movl    $0, %eax
 121
 122         adcl    %ebx, %eax              C further +1 if eax>=ceil(b*2/3)
 123         movl    SAVE_EDI, %edi
 124         movl    SAVE_ESI, %esi
 125
 126         movl    SAVE_EBX, %ebx
 127         addl    $FRAME, %esp
 128
 129         ret
 130
 131 EPILOGUE()