mpn/x86/p6/mul_basecase.asm

   1 dnl  Intel P6 mpn_mul_basecase -- multiply two mpn numbers.
   2
   3 dnl  Copyright 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   4 dnl
   5 dnl  This file is part of the GNU MP Library.
   6 dnl
   7 dnl  The GNU MP Library is free software; you can redistribute it and/or
   8 dnl  modify it under the terms of the GNU Lesser General Public License as
   9 dnl  published by the Free Software Foundation; either version 3 of the
  10 dnl  License, or (at your option) any later version.
  11 dnl
  12 dnl  The GNU MP Library is distributed in the hope that it will be useful,
  13 dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 dnl  Lesser General Public License for more details.
  16 dnl
  17 dnl  You should have received a copy of the GNU Lesser General Public License
  18 dnl  along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.
  19
  20 include(`../config.m4')
  21
  22
  23 C P6: approx 6.5 cycles per cross product (16 limbs/loop unrolling).
  24
  25
  26 dnl  P6 UNROLL_COUNT cycles/product (approx)
  27 dnl           8           7
  28 dnl          16           6.5
  29 dnl          32           6.4
  30 dnl  Maximum possible with the current code is 32.
  31
  32 deflit(UNROLL_COUNT, 16)
  33
  34
  35 C void mpn_mul_basecase (mp_ptr wp,
  36 C                        mp_srcptr xp, mp_size_t xsize,
  37 C                        mp_srcptr yp, mp_size_t ysize);
  38 C
  39 C This routine is essentially the same as mpn/generic/mul_basecase.c, but
  40 C it's faster because it does most of the mpn_addmul_1() startup
  41 C calculations only once.
  42
  43 ifdef(`PIC',`
  44 deflit(UNROLL_THRESHOLD, 5)
  45 ',`
  46 deflit(UNROLL_THRESHOLD, 5)
  47 ')
  48
  49 defframe(PARAM_YSIZE,20)
  50 defframe(PARAM_YP,   16)
  51 defframe(PARAM_XSIZE,12)
  52 defframe(PARAM_XP,   8)
  53 defframe(PARAM_WP,   4)
  54
  55         TEXT
  56         ALIGN(16)
  57
  58 PROLOGUE(mpn_mul_basecase)
  59 deflit(`FRAME',0)
  60
  61         movl    PARAM_XSIZE, %ecx
  62
  63         movl    PARAM_YP, %eax
  64
  65         movl    PARAM_XP, %edx
  66
  67         movl    (%eax), %eax            C yp[0]
  68         cmpl    $2, %ecx
  69         ja      L(xsize_more_than_two)
  70         je      L(two_by_something)
  71
  72
  73         C one limb by one limb
  74
  75         mull    (%edx)
  76
  77         movl    PARAM_WP, %ecx
  78         movl    %eax, (%ecx)
  79         movl    %edx, 4(%ecx)
  80         ret
  81
  82
  83 C -----------------------------------------------------------------------------
  84 L(two_by_something):
  85 deflit(`FRAME',0)
  86
  87 dnl  re-use parameter space
  88 define(SAVE_EBX, `PARAM_XSIZE')
  89 define(SAVE_ESI, `PARAM_YSIZE')
  90
  91         movl    %ebx, SAVE_EBX
  92         cmpl    $1, PARAM_YSIZE
  93         movl    %eax, %ecx              C yp[0]
  94
  95         movl    %esi, SAVE_ESI          C save esi
  96         movl    PARAM_WP, %ebx
  97         movl    %edx, %esi              C xp
  98
  99         movl    (%edx), %eax            C xp[0]
 100         jne     L(two_by_two)
 101
 102
 103         C two limbs by one limb
 104         C
 105         C eax   xp[0]
 106         C ebx   wp
 107         C ecx   yp[0]
 108         C edx
 109         C esi   xp
 110
 111         mull    %ecx
 112
 113         movl    %eax, (%ebx)
 114         movl    4(%esi), %eax
 115         movl    %edx, %esi              C carry
 116
 117         mull    %ecx
 118
 119         addl    %eax, %esi
 120
 121         movl    %esi, 4(%ebx)
 122         movl    SAVE_ESI, %esi
 123
 124         adcl    $0, %edx
 125
 126         movl    %edx, 8(%ebx)
 127         movl    SAVE_EBX, %ebx
 128
 129         ret
 130
 131
 132
 133 C -----------------------------------------------------------------------------
 134
 135         ALIGN(16)
 136 L(two_by_two):
 137         C eax   xp[0]
 138         C ebx   wp
 139         C ecx   yp[0]
 140         C edx
 141         C esi   xp
 142         C edi
 143         C ebp
 144
 145 dnl  more parameter space re-use
 146 define(SAVE_EDI, `PARAM_WP')
 147
 148         mull    %ecx            C xp[0] * yp[0]
 149
 150         movl    %edi, SAVE_EDI
 151         movl    %edx, %edi      C carry, for wp[1]
 152
 153         movl    %eax, (%ebx)
 154         movl    4(%esi), %eax
 155
 156         mull    %ecx            C xp[1] * yp[0]
 157
 158         addl    %eax, %edi
 159         movl    PARAM_YP, %ecx
 160
 161         adcl    $0, %edx
 162         movl    4(%ecx), %ecx   C yp[1]
 163
 164         movl    %edi, 4(%ebx)
 165         movl    4(%esi), %eax   C xp[1]
 166         movl    %edx, %edi      C carry, for wp[2]
 167
 168         mull    %ecx            C xp[1] * yp[1]
 169
 170         addl    %eax, %edi
 171         movl    (%esi), %eax    C xp[0]
 172
 173         adcl    $0, %edx
 174         movl    %edx, %esi      C carry, for wp[3]
 175
 176         mull    %ecx            C xp[0] * yp[1]
 177
 178         addl    %eax, 4(%ebx)
 179         movl    %esi, %eax
 180
 181         adcl    %edx, %edi
 182         movl    SAVE_ESI, %esi
 183
 184         movl    %edi, 8(%ebx)
 185
 186         adcl    $0, %eax
 187         movl    SAVE_EDI, %edi
 188
 189         movl    %eax, 12(%ebx)
 190         movl    SAVE_EBX, %ebx
 191
 192         ret
 193
 194
 195 C -----------------------------------------------------------------------------
 196         ALIGN(16)
 197 L(xsize_more_than_two):
 198
 199 C The first limb of yp is processed with a simple mpn_mul_1 loop running at
 200 C about 6.2 c/l.  Unrolling this doesn't seem worthwhile since it's only run
 201 C once (whereas the addmul_1 below is run ysize-1 many times).  A call to
 202 C mpn_mul_1 would be slowed down by the parameter pushing and popping etc,
 203 C and doesn't seem likely to be worthwhile on the typical sizes reaching
 204 C here from the Karatsuba code.
 205
 206         C eax   yp[0]
 207         C ebx
 208         C ecx   xsize
 209         C edx   xp
 210         C esi
 211         C edi
 212         C ebp
 213
 214 defframe(`SAVE_EBX',    -4)
 215 defframe(`SAVE_ESI',    -8)
 216 defframe(`SAVE_EDI',   -12)
 217 defframe(`SAVE_EBP',   -16)
 218 defframe(VAR_COUNTER,  -20)  dnl for use in the unroll case
 219 defframe(VAR_ADJUST,   -24)
 220 defframe(VAR_JMP,      -28)
 221 defframe(VAR_SWAP,     -32)
 222 defframe(VAR_XP_LOW,   -36)
 223 deflit(STACK_SPACE, 36)
 224
 225         subl    $STACK_SPACE, %esp
 226 deflit(`FRAME',STACK_SPACE)
 227
 228         movl    %edi, SAVE_EDI
 229         movl    PARAM_WP, %edi
 230
 231         movl    %ebx, SAVE_EBX
 232
 233         movl    %ebp, SAVE_EBP
 234         movl    %eax, %ebp
 235
 236         movl    %esi, SAVE_ESI
 237         xorl    %ebx, %ebx
 238         leal    (%edx,%ecx,4), %esi     C xp end
 239
 240         leal    (%edi,%ecx,4), %edi     C wp end of mul1
 241         negl    %ecx
 242
 243
 244 L(mul1):
 245         C eax   scratch
 246         C ebx   carry
 247         C ecx   counter, negative
 248         C edx   scratch
 249         C esi   xp end
 250         C edi   wp end of mul1
 251         C ebp   multiplier
 252
 253         movl    (%esi,%ecx,4), %eax
 254
 255         mull    %ebp
 256
 257         addl    %ebx, %eax
 258         movl    %eax, (%edi,%ecx,4)
 259         movl    $0, %ebx
 260
 261         adcl    %edx, %ebx
 262         incl    %ecx
 263         jnz     L(mul1)
 264
 265
 266         movl    PARAM_YSIZE, %edx
 267
 268         movl    %ebx, (%edi)            C final carry
 269         movl    PARAM_XSIZE, %ecx
 270         decl    %edx
 271
 272         jz      L(done)                 C if ysize==1
 273
 274         cmpl    $UNROLL_THRESHOLD, %ecx
 275         movl    PARAM_YP, %eax
 276         jae     L(unroll)
 277
 278
 279 C -----------------------------------------------------------------------------
 280         C simple addmul looping
 281         C
 282         C eax   yp
 283         C ebx
 284         C ecx   xsize
 285         C edx   ysize-1
 286         C esi   xp end
 287         C edi   wp end of mul1
 288         C ebp
 289
 290         leal    4(%eax,%edx,4), %ebp    C yp end
 291         negl    %ecx
 292         negl    %edx
 293
 294         movl    %edx, PARAM_YSIZE       C -(ysize-1)
 295         movl    (%esi,%ecx,4), %eax     C xp low limb
 296         incl    %ecx
 297
 298         movl    %ecx, PARAM_XSIZE       C -(xsize-1)
 299         xorl    %ebx, %ebx              C initial carry
 300
 301         movl    %ebp, PARAM_YP
 302         movl    (%ebp,%edx,4), %ebp     C yp second lowest limb - multiplier
 303         jmp     L(simple_outer_entry)
 304
 305
 306 L(simple_outer_top):
 307         C ebp   ysize counter, negative
 308
 309         movl    PARAM_YP, %edx
 310
 311         movl    PARAM_XSIZE, %ecx       C -(xsize-1)
 312         xorl    %ebx, %ebx              C carry
 313
 314         movl    %ebp, PARAM_YSIZE
 315         addl    $4, %edi                C next position in wp
 316
 317         movl    (%edx,%ebp,4), %ebp     C yp limb - multiplier
 318
 319         movl    -4(%esi,%ecx,4), %eax   C xp low limb
 320
 321
 322 L(simple_outer_entry):
 323
 324 L(simple_inner_top):
 325         C eax   xp limb
 326         C ebx   carry limb
 327         C ecx   loop counter (negative)
 328         C edx   scratch
 329         C esi   xp end
 330         C edi   wp end
 331         C ebp   multiplier
 332
 333         mull    %ebp
 334
 335         addl    %eax, %ebx
 336         adcl    $0, %edx
 337
 338         addl    %ebx, (%edi,%ecx,4)
 339         movl    (%esi,%ecx,4), %eax
 340         adcl    $0, %edx
 341
 342         incl    %ecx
 343         movl    %edx, %ebx
 344         jnz     L(simple_inner_top)
 345
 346
 347         C separate code for last limb so outer loop counter handling can be
 348         C interleaved
 349
 350         mull    %ebp
 351
 352         movl    PARAM_YSIZE, %ebp
 353         addl    %eax, %ebx
 354
 355         adcl    $0, %edx
 356
 357         addl    %ebx, (%edi)
 358
 359         adcl    $0, %edx
 360         incl    %ebp
 361
 362         movl    %edx, 4(%edi)
 363         jnz     L(simple_outer_top)
 364
 365
 366 L(done):
 367         movl    SAVE_EBX, %ebx
 368
 369         movl    SAVE_ESI, %esi
 370
 371         movl    SAVE_EDI, %edi
 372
 373         movl    SAVE_EBP, %ebp
 374         addl    $FRAME, %esp
 375
 376         ret
 377
 378
 379
 380 C -----------------------------------------------------------------------------
 381 C
 382 C The unrolled loop is the same as in mpn_addmul_1, see that code for some
 383 C comments.
 384 C
 385 C VAR_ADJUST is the negative of how many limbs the leals in the inner loop
 386 C increment xp and wp.  This is used to adjust xp and wp, and is rshifted to
 387 C given an initial VAR_COUNTER at the top of the outer loop.
 388 C
 389 C VAR_COUNTER is for the unrolled loop, running from VAR_ADJUST/UNROLL_COUNT
 390 C up to -1, inclusive.
 391 C
 392 C VAR_JMP is the computed jump into the unrolled loop.
 393 C
 394 C VAR_SWAP is 0 if xsize odd or 0xFFFFFFFF if xsize even, used to swap the
 395 C initial ebx and ecx on entry to the unrolling.
 396 C
 397 C VAR_XP_LOW is the least significant limb of xp, which is needed at the
 398 C start of the unrolled loop.
 399 C
 400 C PARAM_YSIZE is the outer loop counter, going from -(ysize-1) up to -1,
 401 C inclusive.
 402 C
 403 C PARAM_YP is offset appropriately so that the PARAM_YSIZE counter can be
 404 C added to give the location of the next limb of yp, which is the multiplier
 405 C in the unrolled loop.
 406 C
 407 C The trick with the VAR_ADJUST value means it's only necessary to do one
 408 C fetch in the outer loop to take care of xp, wp and the inner loop counter.
 409
 410
 411 L(unroll):
 412         C eax   yp
 413         C ebx
 414         C ecx   xsize
 415         C edx   ysize-1
 416         C esi   xp end
 417         C edi   wp end of mul1
 418         C ebp
 419
 420         movl    PARAM_XP, %esi
 421
 422         movl    4(%eax), %ebp           C multiplier (yp second limb)
 423         leal    4(%eax,%edx,4), %eax    C yp adjust for ysize indexing
 424
 425         movl    %eax, PARAM_YP
 426         movl    PARAM_WP, %edi
 427         negl    %edx
 428
 429         movl    %edx, PARAM_YSIZE
 430         leal    UNROLL_COUNT-2(%ecx), %ebx      C (xsize-1)+UNROLL_COUNT-1
 431         decl    %ecx                            C xsize-1
 432
 433         movl    (%esi), %eax            C xp low limb
 434         andl    $-UNROLL_MASK-1, %ebx
 435         negl    %ecx                    C -(xsize-1)
 436
 437         negl    %ebx
 438         andl    $UNROLL_MASK, %ecx
 439
 440         movl    %ebx, VAR_ADJUST
 441         movl    %ecx, %edx
 442         shll    $4, %ecx
 443
 444         movl    %eax, VAR_XP_LOW
 445         sarl    $UNROLL_LOG2, %ebx
 446         negl    %edx
 447
 448         C 15 code bytes per limb
 449 ifdef(`PIC',`
 450         call    L(pic_calc)
 451 L(unroll_here):
 452 ',`
 453         leal    L(unroll_inner_entry) (%ecx,%edx,1), %ecx
 454 ')
 455
 456         movl    %ecx, VAR_JMP
 457         movl    %edx, %ecx
 458         shll    $31, %edx
 459
 460         sarl    $31, %edx               C 0 or -1 as xsize odd or even
 461         leal    4(%edi,%ecx,4), %edi    C wp and xp, adjust for unrolling,
 462         leal    4(%esi,%ecx,4), %esi    C  and start at second limb
 463
 464         movl    %edx, VAR_SWAP
 465         jmp     L(unroll_outer_entry)
 466
 467
 468 ifdef(`PIC',`
 469 L(pic_calc):
 470         C See mpn/x86/README about old gas bugs
 471         leal    (%ecx,%edx,1), %ecx
 472         addl    $L(unroll_inner_entry)-L(unroll_here), %ecx
 473         addl    (%esp), %ecx
 474         ret_internal
 475 ')
 476
 477
 478 C --------------------------------------------------------------------------
 479         ALIGN(16)
 480 L(unroll_outer_top):
 481         C eax
 482         C ebx
 483         C ecx
 484         C edx
 485         C esi   xp + offset
 486         C edi   wp + offset
 487         C ebp   ysize counter, negative
 488
 489         movl    VAR_ADJUST, %ebx
 490         movl    PARAM_YP, %edx
 491
 492         movl    VAR_XP_LOW, %eax
 493         movl    %ebp, PARAM_YSIZE       C store incremented ysize counter
 494
 495         leal    eval(UNROLL_BYTES + 4) (%edi,%ebx,4), %edi
 496         leal    (%esi,%ebx,4), %esi
 497         sarl    $UNROLL_LOG2, %ebx
 498
 499         movl    (%edx,%ebp,4), %ebp     C yp next multiplier
 500
 501 L(unroll_outer_entry):
 502         mull    %ebp
 503
 504         movl    %ebx, VAR_COUNTER
 505         movl    %edx, %ebx              C carry high
 506         movl    %eax, %ecx              C carry low
 507
 508         xorl    %edx, %eax
 509         movl    VAR_JMP, %edx
 510
 511         andl    VAR_SWAP, %eax
 512
 513         xorl    %eax, %ebx              C carries other way for odd index
 514         xorl    %eax, %ecx
 515
 516         jmp     *%edx
 517
 518
 519 C -----------------------------------------------------------------------------
 520
 521 L(unroll_inner_top):
 522         C eax   xp limb
 523         C ebx   carry high
 524         C ecx   carry low
 525         C edx   scratch
 526         C esi   xp+8
 527         C edi   wp
 528         C ebp   yp multiplier limb
 529         C
 530         C VAR_COUNTER  loop counter, negative
 531         C
 532         C 15 bytes each limb
 533
 534         addl    $UNROLL_BYTES, %edi
 535
 536 L(unroll_inner_entry):
 537
 538 deflit(CHUNK_COUNT,2)
 539 forloop(`i', 0, UNROLL_COUNT/CHUNK_COUNT-1, `
 540         deflit(`disp0', eval(i*CHUNK_COUNT*4 ifelse(UNROLL_BYTES,256,-128)))
 541         deflit(`disp1', eval(disp0 + 4))
 542
 543 Zdisp(  movl,   disp0,(%esi), %eax)
 544         mull    %ebp
 545 Zdisp(  addl,   %ecx, disp0,(%edi))
 546         adcl    %eax, %ebx              C new carry low
 547         movl    %edx, %ecx
 548         adcl    $0, %ecx                C new carry high
 549
 550         movl    disp1(%esi), %eax
 551         mull    %ebp
 552         addl    %ebx, disp1(%edi)
 553         adcl    %eax, %ecx              C new carry low
 554         movl    %edx, %ebx
 555         adcl    $0, %ebx                C new carry high
 556 ')
 557
 558
 559         incl    VAR_COUNTER
 560         leal    UNROLL_BYTES(%esi), %esi
 561         jnz     L(unroll_inner_top)
 562
 563
 564         C eax
 565         C ebx   carry high
 566         C ecx   carry low
 567         C edx
 568         C esi
 569         C edi   wp, pointing at second last limb)
 570         C ebp
 571
 572 deflit(`disp0', eval(UNROLL_BYTES ifelse(UNROLL_BYTES,256,-128)))
 573 deflit(`disp1', eval(disp0 + 4))
 574
 575         movl    PARAM_YSIZE, %ebp
 576         addl    %ecx, disp0(%edi)       C carry low
 577
 578         adcl    $0, %ebx
 579         incl    %ebp
 580
 581         movl    %ebx, disp1(%edi)       C carry high
 582         jnz     L(unroll_outer_top)
 583
 584
 585         movl    SAVE_ESI, %esi
 586
 587         movl    SAVE_EBP, %ebp
 588
 589         movl    SAVE_EDI, %edi
 590
 591         movl    SAVE_EBX, %ebx
 592         addl    $FRAME, %esp
 593
 594         ret
 595
 596 EPILOGUE()