mpn/x86/k7/mmx/popham.asm

   1 dnl  AMD K7 mpn_popcount, mpn_hamdist -- population count and hamming
   2 dnl  distance.
   3
   4 dnl  Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
   5 dnl
   6 dnl  This file is part of the GNU MP Library.
   7 dnl
   8 dnl  The GNU MP Library is free software; you can redistribute it and/or
   9 dnl  modify it under the terms of the GNU Lesser General Public License as
  10 dnl  published by the Free Software Foundation; either version 3 of the
  11 dnl  License, or (at your option) any later version.
  12 dnl
  13 dnl  The GNU MP Library is distributed in the hope that it will be useful,
  14 dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 dnl  Lesser General Public License for more details.
  17 dnl
  18 dnl  You should have received a copy of the GNU Lesser General Public License
  19 dnl  along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.
  20
  21 include(`../config.m4')
  22
  23
  24 C                            popcount        hamdist
  25 C P3 generic                    6.5             7
  26 C P3 model 9  (Banias)          ?               ?
  27 C P3 model 13 (Dothan)          5.75            6
  28 C K7                            5               6
  29
  30 C unsigned long mpn_popcount (mp_srcptr src, mp_size_t size);
  31 C unsigned long mpn_hamdist (mp_srcptr src, mp_srcptr src2, mp_size_t size);
  32 C
  33 C The code here is almost certainly not optimal, but is already a 3x speedup
  34 C over the generic C code.  The main improvement would be to interleave
  35 C processing of two qwords in the loop so as to fully exploit the available
  36 C execution units, possibly leading to 3.25 c/l (13 cycles for 4 limbs).
  37 C
  38 C The loop is based on the example "Efficient 64-bit population count using
  39 C MMX instructions" in the Athlon Optimization Guide, AMD document 22007,
  40 C page 158 of rev E (reference in mpn/x86/k7/README).
  41
  42 ifdef(`OPERATION_popcount',,
  43 `ifdef(`OPERATION_hamdist',,
  44 `m4_error(`Need OPERATION_popcount or OPERATION_hamdist defined
  45 ')')')
  46
  47 define(HAM,
  48 m4_assert_numargs(1)
  49 `ifdef(`OPERATION_hamdist',`$1')')
  50
  51 define(POP,
  52 m4_assert_numargs(1)
  53 `ifdef(`OPERATION_popcount',`$1')')
  54
  55 HAM(`
  56 defframe(PARAM_SIZE,   12)
  57 defframe(PARAM_SRC2,   8)
  58 defframe(PARAM_SRC,    4)
  59 define(M4_function,mpn_hamdist)
  60 ')
  61 POP(`
  62 defframe(PARAM_SIZE,   8)
  63 defframe(PARAM_SRC,    4)
  64 define(M4_function,mpn_popcount)
  65 ')
  66
  67 MULFUNC_PROLOGUE(mpn_popcount mpn_hamdist)
  68
  69
  70 ifdef(`PIC',,`
  71         dnl  non-PIC
  72
  73         RODATA
  74         ALIGN(8)
  75
  76 L(rodata_AAAAAAAAAAAAAAAA):
  77         .long   0xAAAAAAAA
  78         .long   0xAAAAAAAA
  79
  80 L(rodata_3333333333333333):
  81         .long   0x33333333
  82         .long   0x33333333
  83
  84 L(rodata_0F0F0F0F0F0F0F0F):
  85         .long   0x0F0F0F0F
  86         .long   0x0F0F0F0F
  87 ')
  88
  89         TEXT
  90         ALIGN(32)
  91
  92 PROLOGUE(M4_function)
  93 deflit(`FRAME',0)
  94
  95         movl    PARAM_SIZE, %ecx
  96
  97 ifdef(`PIC',`
  98         movl    $0xAAAAAAAA, %eax
  99         movl    $0x33333333, %edx
 100
 101         movd    %eax, %mm7
 102         movd    %edx, %mm6
 103
 104         movl    $0x0F0F0F0F, %eax
 105
 106         punpckldq %mm7, %mm7
 107         punpckldq %mm6, %mm6
 108
 109         movd    %eax, %mm5
 110         movd    %edx, %mm4
 111
 112         punpckldq %mm5, %mm5
 113
 114 ',`
 115         movq    L(rodata_AAAAAAAAAAAAAAAA), %mm7
 116         movq    L(rodata_3333333333333333), %mm6
 117         movq    L(rodata_0F0F0F0F0F0F0F0F), %mm5
 118 ')
 119         pxor    %mm4, %mm4
 120
 121 define(REG_AAAAAAAAAAAAAAAA,%mm7)
 122 define(REG_3333333333333333,%mm6)
 123 define(REG_0F0F0F0F0F0F0F0F,%mm5)
 124 define(REG_0000000000000000,%mm4)
 125
 126
 127         movl    PARAM_SRC, %eax
 128 HAM(`   movl    PARAM_SRC2, %edx')
 129
 130         pxor    %mm2, %mm2      C total
 131
 132         shrl    %ecx
 133         jnc     L(top)
 134
 135         movd    (%eax,%ecx,8), %mm1
 136
 137 HAM(`   movd    (%edx,%ecx,8), %mm0
 138         pxor    %mm0, %mm1
 139 ')
 140         orl     %ecx, %ecx
 141         jmp     L(loaded)
 142
 143
 144         ALIGN(16)
 145 L(top):
 146         C eax   src
 147         C ebx
 148         C ecx   counter, qwords, decrementing
 149         C edx   [hamdist] src2
 150         C
 151         C mm0   (scratch)
 152         C mm1   (scratch)
 153         C mm2   total (low dword)
 154         C mm3
 155         C mm4   \
 156         C mm5   | special constants
 157         C mm6   |
 158         C mm7   /
 159
 160         movq    -8(%eax,%ecx,8), %mm1
 161
 162 HAM(`   pxor    -8(%edx,%ecx,8), %mm1')
 163         decl    %ecx
 164
 165 L(loaded):
 166         movq    %mm1, %mm0
 167         pand    REG_AAAAAAAAAAAAAAAA, %mm1
 168
 169         psrlq   $1, %mm1
 170
 171         psubd   %mm1, %mm0      C bit pairs
 172
 173
 174         movq    %mm0, %mm1
 175         psrlq   $2, %mm0
 176
 177         pand    REG_3333333333333333, %mm0
 178         pand    REG_3333333333333333, %mm1
 179
 180         paddd   %mm1, %mm0      C nibbles
 181
 182
 183         movq    %mm0, %mm1
 184         psrlq   $4, %mm0
 185
 186         pand    REG_0F0F0F0F0F0F0F0F, %mm0
 187         pand    REG_0F0F0F0F0F0F0F0F, %mm1
 188
 189         paddd   %mm1, %mm0      C bytes
 190
 191
 192         psadbw( %mm4, %mm0)
 193
 194         paddd   %mm0, %mm2      C add to total
 195         jnz     L(top)
 196
 197
 198         movd    %mm2, %eax
 199         emms
 200         ret
 201
 202 EPILOGUE()