arch/x86/lib/hweight.S

   1 #include <linux/linkage.h>
   2 #include <asm/export.h>
   3
   4 #include <asm/asm.h>
   5
   6 /*
   7  * unsigned int __sw_hweight32(unsigned int w)
   8  * %rdi: w
   9  */
  10 ENTRY(__sw_hweight32)
  11
  12 #ifdef CONFIG_X86_64
  13         movl %edi, %eax                         # w
  14 #endif
  15         __ASM_SIZE(push,) %__ASM_REG(dx)
  16         movl %eax, %edx                         # w -> t
  17         shrl %edx                               # t >>= 1
  18         andl $0x55555555, %edx                  # t &= 0x55555555
  19         subl %edx, %eax                         # w -= t
  20
  21         movl %eax, %edx                         # w -> t
  22         shrl $2, %eax                           # w_tmp >>= 2
  23         andl $0x33333333, %edx                  # t     &= 0x33333333
  24         andl $0x33333333, %eax                  # w_tmp &= 0x33333333
  25         addl %edx, %eax                         # w = w_tmp + t
  26
  27         movl %eax, %edx                         # w -> t
  28         shrl $4, %edx                           # t >>= 4
  29         addl %edx, %eax                         # w_tmp += t
  30         andl  $0x0f0f0f0f, %eax                 # w_tmp &= 0x0f0f0f0f
  31         imull $0x01010101, %eax, %eax           # w_tmp *= 0x01010101
  32         shrl $24, %eax                          # w = w_tmp >> 24
  33         __ASM_SIZE(pop,) %__ASM_REG(dx)
  34         ret
  35 ENDPROC(__sw_hweight32)
  36 EXPORT_SYMBOL(__sw_hweight32)
  37
  38 ENTRY(__sw_hweight64)
  39 #ifdef CONFIG_X86_64
  40         pushq   %rdi
  41         pushq   %rdx
  42
  43         movq    %rdi, %rdx                      # w -> t
  44         movabsq $0x5555555555555555, %rax
  45         shrq    %rdx                            # t >>= 1
  46         andq    %rdx, %rax                      # t &= 0x5555555555555555
  47         movabsq $0x3333333333333333, %rdx
  48         subq    %rax, %rdi                      # w -= t
  49
  50         movq    %rdi, %rax                      # w -> t
  51         shrq    $2, %rdi                        # w_tmp >>= 2
  52         andq    %rdx, %rax                      # t     &= 0x3333333333333333
  53         andq    %rdi, %rdx                      # w_tmp &= 0x3333333333333333
  54         addq    %rdx, %rax                      # w = w_tmp + t
  55
  56         movq    %rax, %rdx                      # w -> t
  57         shrq    $4, %rdx                        # t >>= 4
  58         addq    %rdx, %rax                      # w_tmp += t
  59         movabsq $0x0f0f0f0f0f0f0f0f, %rdx
  60         andq    %rdx, %rax                      # w_tmp &= 0x0f0f0f0f0f0f0f0f
  61         movabsq $0x0101010101010101, %rdx
  62         imulq   %rdx, %rax                      # w_tmp *= 0x0101010101010101
  63         shrq    $56, %rax                       # w = w_tmp >> 56
  64
  65         popq    %rdx
  66         popq    %rdi
  67         ret
  68 #else /* CONFIG_X86_32 */
  69         /* We're getting an u64 arg in (%eax,%edx): unsigned long hweight64(__u64 w) */
  70         pushl   %ecx
  71
  72         call    __sw_hweight32
  73         movl    %eax, %ecx                      # stash away result
  74         movl    %edx, %eax                      # second part of input
  75         call    __sw_hweight32
  76         addl    %ecx, %eax                      # result
  77
  78         popl    %ecx
  79         ret
  80 #endif
  81 ENDPROC(__sw_hweight64)
  82 EXPORT_SYMBOL(__sw_hweight64)