mpn/x86_64/k10/popcount.asm

   1 dnl  AMD64 mpn_popcount -- population count.
   2
   3 dnl  Copyright 2008, 2010-2012 Free Software Foundation, Inc.
   4
   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 modify
   8 dnl  it under the terms of either:
   9 dnl
  10 dnl    * the GNU Lesser General Public License as published by the Free
  11 dnl      Software Foundation; either version 3 of the License, or (at your
  12 dnl      option) any later version.
  13 dnl
  14 dnl  or
  15 dnl
  16 dnl    * the GNU General Public License as published by the Free Software
  17 dnl      Foundation; either version 2 of the License, or (at your option) any
  18 dnl      later version.
  19 dnl
  20 dnl  or both in parallel, as here.
  21 dnl
  22 dnl  The GNU MP Library is distributed in the hope that it will be useful, but
  23 dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  24 dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  25 dnl  for more details.
  26 dnl
  27 dnl  You should have received copies of the GNU General Public License and the
  28 dnl  GNU Lesser General Public License along with the GNU MP Library.  If not,
  29 dnl  see https://www.gnu.org/licenses/.
  30
  31 include(`../config.m4')
  32
  33 C                   cycles/limb
  34 C AMD K8,K9              n/a
  35 C AMD K10                1.125
  36 C Intel P4               n/a
  37 C Intel core2            n/a
  38 C Intel corei            1.25
  39 C Intel atom             n/a
  40 C VIA nano               n/a
  41
  42 C * The zero-offset of popcount is misassembled to the offset-less form, which
  43 C   is one byte shorter and therefore will mess up the switching code.
  44 C * The outdated gas used in FreeBSD and NetBSD cannot handle the POPCNT insn,
  45 C   which is the main reason for our usage of '.byte'.
  46
  47 C TODO
  48 C  * Improve switching code, the current code sucks.
  49
  50 define(`up',            `%rdi')
  51 define(`n',             `%rsi')
  52
  53 ABI_SUPPORT(DOS64)
  54 ABI_SUPPORT(STD64)
  55
  56 ASM_START()
  57         TEXT
  58         ALIGN(32)
  59 PROLOGUE(mpn_popcount)
  60         FUNC_ENTRY(2)
  61
  62 ifelse(1,1,`
  63         lea     (up,n,8), up
  64
  65 C       mov     R32(n), R32(%rcx)
  66 C       neg     R32(%rcx)
  67         imul    $-1, R32(n), R32(%rcx)
  68         and     $8-1, R32(%rcx)
  69
  70         neg     n
  71
  72         mov     R32(%rcx), R32(%rax)
  73         neg     %rax
  74         lea     (up,%rax,8),up
  75
  76         xor     R32(%rax), R32(%rax)
  77
  78         lea     (%rcx,%rcx,4), %rcx
  79
  80         lea     L(top)(%rip), %rdx
  81         lea     (%rdx,%rcx,2), %rdx
  82         jmp     *%rdx
  83 ',`
  84         lea     (up,n,8), up
  85
  86         mov     R32(n), R32(%rcx)
  87         neg     R32(%rcx)
  88         and     $8-1, R32(%rcx)
  89
  90         neg     n
  91
  92         mov     R32(%rcx), R32(%rax)
  93         shl     $3, R32(%rax)
  94         sub     %rax, up
  95
  96         xor     R32(%rax), R32(%rax)
  97
  98 C       add     R32(%rcx), R32(%rcx)    C 2x
  99 C       lea     (%rcx,%rcx,4), %rcx     C 10x
 100         imul    $10, R32(%rcx)
 101
 102         lea     L(top)(%rip), %rdx
 103         add     %rcx, %rdx
 104         jmp     *%rdx
 105 ')
 106
 107         ALIGN(32)
 108 L(top):
 109 C 0 = n mod 8
 110         .byte   0xf3,0x4c,0x0f,0xb8,0x44,0xf7,0x00      C popcnt 0(up,n,8), %r8
 111         add     %r8, %rax
 112 C 7 = n mod 8
 113         .byte   0xf3,0x4c,0x0f,0xb8,0x4c,0xf7,0x08      C popcnt 8(up,n,8), %r9
 114         add     %r9, %rax
 115 C 6 = n mod 8
 116         .byte   0xf3,0x4c,0x0f,0xb8,0x44,0xf7,0x10      C popcnt 16(up,n,8), %r8
 117         add     %r8, %rax
 118 C 5 = n mod 8
 119         .byte   0xf3,0x4c,0x0f,0xb8,0x4c,0xf7,0x18      C popcnt 24(up,n,8), %r9
 120         add     %r9, %rax
 121 C 4 = n mod 8
 122         .byte   0xf3,0x4c,0x0f,0xb8,0x44,0xf7,0x20      C popcnt 32(up,n,8), %r8
 123         add     %r8, %rax
 124 C 3 = n mod 8
 125         .byte   0xf3,0x4c,0x0f,0xb8,0x4c,0xf7,0x28      C popcnt 40(up,n,8), %r9
 126         add     %r9, %rax
 127 C 2 = n mod 8
 128         .byte   0xf3,0x4c,0x0f,0xb8,0x44,0xf7,0x30      C popcnt 48(up,n,8), %r8
 129         add     %r8, %rax
 130 C 1 = n mod 8
 131         .byte   0xf3,0x4c,0x0f,0xb8,0x4c,0xf7,0x38      C popcnt 56(up,n,8), %r9
 132         add     %r9, %rax
 133
 134         add     $8, n
 135         js      L(top)
 136         FUNC_EXIT()
 137         ret
 138 EPILOGUE()