Hex Artifact Content
Not logged in

Artifact 11874b577f5729c46052ad88a02afba9ac7f2306:


0000: 2f 2a 20 3d 3d 3d 2d 2d 20 70 6f 70 63 6f 75 6e  /* ===-- popcoun
0010: 74 74 69 32 2e 63 20 2d 20 49 6d 70 6c 65 6d 65  tti2.c - Impleme
0020: 6e 74 20 5f 5f 70 6f 70 63 6f 75 6e 74 74 69 32  nt __popcountti2
0030: 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d   ---------------
0040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 3d 3d 3d  -------------===
0050: 0a 20 2a 0a 20 2a 20 20 20 20 20 20 20 20 20 20  . *. *          
0060: 20 20 20 20 20 20 20 20 20 20 20 54 68 65 20 4c             The L
0070: 4c 56 4d 20 43 6f 6d 70 69 6c 65 72 20 49 6e 66  LVM Compiler Inf
0080: 72 61 73 74 72 75 63 74 75 72 65 0a 20 2a 0a 20  rastructure. *. 
0090: 2a 20 54 68 69 73 20 66 69 6c 65 20 69 73 20 64  * This file is d
00a0: 75 61 6c 20 6c 69 63 65 6e 73 65 64 20 75 6e 64  ual licensed und
00b0: 65 72 20 74 68 65 20 4d 49 54 20 61 6e 64 20 74  er the MIT and t
00c0: 68 65 20 55 6e 69 76 65 72 73 69 74 79 20 6f 66  he University of
00d0: 20 49 6c 6c 69 6e 6f 69 73 20 4f 70 65 6e 0a 20   Illinois Open. 
00e0: 2a 20 53 6f 75 72 63 65 20 4c 69 63 65 6e 73 65  * Source License
00f0: 73 2e 20 53 65 65 20 4c 49 43 45 4e 53 45 2e 54  s. See LICENSE.T
0100: 58 54 20 66 6f 72 20 64 65 74 61 69 6c 73 2e 0a  XT for details..
0110: 20 2a 0a 20 2a 20 3d 3d 3d 2d 2d 2d 2d 2d 2d 2d   *. * ===-------
0120: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0150: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 3d  ---------------=
0160: 3d 3d 0a 20 2a 0a 20 2a 20 54 68 69 73 20 66 69  ==. *. * This fi
0170: 6c 65 20 69 6d 70 6c 65 6d 65 6e 74 73 20 5f 5f  le implements __
0180: 70 6f 70 63 6f 75 6e 74 74 69 32 20 66 6f 72 20  popcountti2 for 
0190: 74 68 65 20 63 6f 6d 70 69 6c 65 72 5f 72 74 20  the compiler_rt 
01a0: 6c 69 62 72 61 72 79 2e 0a 20 2a 0a 20 2a 20 3d  library.. *. * =
01b0: 3d 3d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ==--------------
01c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
01f0: 2d 2d 2d 2d 2d 2d 2d 2d 3d 3d 3d 0a 20 2a 2f 0a  --------===. */.
0200: 0a 23 69 6e 63 6c 75 64 65 20 22 69 6e 74 5f 6c  .#include "int_l
0210: 69 62 2e 68 22 0a 0a 23 69 66 64 65 66 20 43 52  ib.h"..#ifdef CR
0220: 54 5f 48 41 53 5f 31 32 38 42 49 54 0a 0a 2f 2a  T_HAS_128BIT../*
0230: 20 52 65 74 75 72 6e 73 3a 20 63 6f 75 6e 74 20   Returns: count 
0240: 6f 66 20 31 20 62 69 74 73 20 2a 2f 0a 0a 43 4f  of 1 bits */..CO
0250: 4d 50 49 4c 45 52 5f 52 54 5f 41 42 49 20 73 69  MPILER_RT_ABI si
0260: 5f 69 6e 74 0a 5f 5f 70 6f 70 63 6f 75 6e 74 74  _int.__popcountt
0270: 69 32 28 74 69 5f 69 6e 74 20 61 29 0a 7b 0a 20  i2(ti_int a).{. 
0280: 20 20 20 74 75 5f 69 6e 74 20 78 33 20 3d 20 28     tu_int x3 = (
0290: 74 75 5f 69 6e 74 29 61 3b 0a 20 20 20 20 78 33  tu_int)a;.    x3
02a0: 20 3d 20 78 33 20 2d 20 28 28 78 33 20 3e 3e 20   = x3 - ((x3 >> 
02b0: 31 29 20 26 20 28 28 28 74 75 5f 69 6e 74 29 30  1) & (((tu_int)0
02c0: 78 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35  x555555555555555
02d0: 35 75 4c 4c 20 3c 3c 20 36 34 29 20 7c 0a 20 20  5uLL << 64) |.  
02e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
02f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0300: 20 20 20 30 78 35 35 35 35 35 35 35 35 35 35 35     0x55555555555
0310: 35 35 35 35 35 75 4c 4c 29 29 3b 0a 20 20 20 20  55555uLL));.    
0320: 2f 2a 20 45 76 65 72 79 20 32 20 62 69 74 73 20  /* Every 2 bits 
0330: 68 6f 6c 64 73 20 74 68 65 20 73 75 6d 20 6f 66  holds the sum of
0340: 20 65 76 65 72 79 20 70 61 69 72 20 6f 66 20 62   every pair of b
0350: 69 74 73 20 28 36 34 29 20 2a 2f 0a 20 20 20 20  its (64) */.    
0360: 78 33 20 3d 20 28 28 78 33 20 3e 3e 20 32 29 20  x3 = ((x3 >> 2) 
0370: 26 20 28 28 28 74 75 5f 69 6e 74 29 30 78 33 33  & (((tu_int)0x33
0380: 33 33 33 33 33 33 33 33 33 33 33 33 33 33 75 4c  33333333333333uL
0390: 4c 20 3c 3c 20 36 34 29 20 7c 20 30 78 33 33 33  L << 64) | 0x333
03a0: 33 33 33 33 33 33 33 33 33 33 33 33 33 75 4c 4c  3333333333333uLL
03b0: 29 29 0a 20 20 20 20 20 20 20 2b 20 28 78 33 20  )).       + (x3 
03c0: 26 20 28 28 28 74 75 5f 69 6e 74 29 30 78 33 33  & (((tu_int)0x33
03d0: 33 33 33 33 33 33 33 33 33 33 33 33 33 33 75 4c  33333333333333uL
03e0: 4c 20 3c 3c 20 36 34 29 20 7c 20 30 78 33 33 33  L << 64) | 0x333
03f0: 33 33 33 33 33 33 33 33 33 33 33 33 33 75 4c 4c  3333333333333uLL
0400: 29 29 3b 0a 20 20 20 20 2f 2a 20 45 76 65 72 79  ));.    /* Every
0410: 20 34 20 62 69 74 73 20 68 6f 6c 64 73 20 74 68   4 bits holds th
0420: 65 20 73 75 6d 20 6f 66 20 65 76 65 72 79 20 34  e sum of every 4
0430: 2d 73 65 74 20 6f 66 20 62 69 74 73 20 28 33 20  -set of bits (3 
0440: 73 69 67 6e 69 66 69 63 61 6e 74 20 62 69 74 73  significant bits
0450: 29 20 28 33 32 29 20 2a 2f 0a 20 20 20 20 78 33  ) (32) */.    x3
0460: 20 3d 20 28 78 33 20 2b 20 28 78 33 20 3e 3e 20   = (x3 + (x3 >> 
0470: 34 29 29 0a 20 20 20 20 20 20 20 26 20 28 28 28  4)).       & (((
0480: 74 75 5f 69 6e 74 29 30 78 30 46 30 46 30 46 30  tu_int)0x0F0F0F0
0490: 46 30 46 30 46 30 46 30 46 75 4c 4c 20 3c 3c 20  F0F0F0F0FuLL << 
04a0: 36 34 29 20 7c 20 30 78 30 46 30 46 30 46 30 46  64) | 0x0F0F0F0F
04b0: 30 46 30 46 30 46 30 46 75 4c 4c 29 3b 0a 20 20  0F0F0F0FuLL);.  
04c0: 20 20 2f 2a 20 45 76 65 72 79 20 38 20 62 69 74    /* Every 8 bit
04d0: 73 20 68 6f 6c 64 73 20 74 68 65 20 73 75 6d 20  s holds the sum 
04e0: 6f 66 20 65 76 65 72 79 20 38 2d 73 65 74 20 6f  of every 8-set o
04f0: 66 20 62 69 74 73 20 28 34 20 73 69 67 6e 69 66  f bits (4 signif
0500: 69 63 61 6e 74 20 62 69 74 73 29 20 28 31 36 29  icant bits) (16)
0510: 20 2a 2f 0a 20 20 20 20 64 75 5f 69 6e 74 20 78   */.    du_int x
0520: 32 20 3d 20 28 64 75 5f 69 6e 74 29 28 78 33 20  2 = (du_int)(x3 
0530: 2b 20 28 78 33 20 3e 3e 20 36 34 29 29 3b 0a 20  + (x3 >> 64));. 
0540: 20 20 20 2f 2a 20 45 76 65 72 79 20 38 20 62 69     /* Every 8 bi
0550: 74 73 20 68 6f 6c 64 73 20 74 68 65 20 73 75 6d  ts holds the sum
0560: 20 6f 66 20 65 76 65 72 79 20 38 2d 73 65 74 20   of every 8-set 
0570: 6f 66 20 62 69 74 73 20 28 35 20 73 69 67 6e 69  of bits (5 signi
0580: 66 69 63 61 6e 74 20 62 69 74 73 29 20 28 38 29  ficant bits) (8)
0590: 20 2a 2f 0a 20 20 20 20 73 75 5f 69 6e 74 20 78   */.    su_int x
05a0: 20 3d 20 28 73 75 5f 69 6e 74 29 28 78 32 20 2b   = (su_int)(x2 +
05b0: 20 28 78 32 20 3e 3e 20 33 32 29 29 3b 0a 20 20   (x2 >> 32));.  
05c0: 20 20 2f 2a 20 45 76 65 72 79 20 38 20 62 69 74    /* Every 8 bit
05d0: 73 20 68 6f 6c 64 73 20 74 68 65 20 73 75 6d 20  s holds the sum 
05e0: 6f 66 20 65 76 65 72 79 20 38 2d 73 65 74 20 6f  of every 8-set o
05f0: 66 20 62 69 74 73 20 28 36 20 73 69 67 6e 69 66  f bits (6 signif
0600: 69 63 61 6e 74 20 62 69 74 73 29 20 28 34 29 20  icant bits) (4) 
0610: 2a 2f 0a 20 20 20 20 78 20 3d 20 78 20 2b 20 28  */.    x = x + (
0620: 78 20 3e 3e 20 31 36 29 3b 0a 20 20 20 20 2f 2a  x >> 16);.    /*
0630: 20 45 76 65 72 79 20 38 20 62 69 74 73 20 68 6f   Every 8 bits ho
0640: 6c 64 73 20 74 68 65 20 73 75 6d 20 6f 66 20 65  lds the sum of e
0650: 76 65 72 79 20 38 2d 73 65 74 20 6f 66 20 62 69  very 8-set of bi
0660: 74 73 20 28 37 20 73 69 67 6e 69 66 69 63 61 6e  ts (7 significan
0670: 74 20 62 69 74 73 29 20 28 32 29 20 2a 2f 0a 20  t bits) (2) */. 
0680: 20 20 20 2f 2a 20 55 70 70 65 72 20 31 36 20 62     /* Upper 16 b
0690: 69 74 73 20 61 72 65 20 67 61 72 62 61 67 65 20  its are garbage 
06a0: 2a 2f 0a 20 20 20 20 72 65 74 75 72 6e 20 28 78  */.    return (x
06b0: 20 2b 20 28 78 20 3e 3e 20 38 29 29 20 26 20 30   + (x >> 8)) & 0
06c0: 78 46 46 3b 20 20 2f 2a 20 28 38 20 73 69 67 6e  xFF;  /* (8 sign
06d0: 69 66 69 63 61 6e 74 20 62 69 74 73 29 20 2a 2f  ificant bits) */
06e0: 0a 7d 0a 0a 23 65 6e 64 69 66 20 2f 2a 20 43 52  .}..#endif /* CR
06f0: 54 5f 48 41 53 5f 31 32 38 42 49 54 20 2a 2f 0a  T_HAS_128BIT */.