-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathLn.cs
193 lines (180 loc) · 14.4 KB
/
Ln.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
using System;
namespace CRUSH_Selection_Algorithm_Test
{
/// <summary>
/// Copied from https://github.com/ceph/ceph/blob/master/src/crush/crush_ln_table.h
/// and https://github.com/ceph/ceph/blob/master/src/crush/mapper.c#L257
/// </summary>
public static class Ln
{
// compute 2^44*log2(input+1)
public static Int64 Get(uint xin)
{
uint x = xin, x1;
int iexpon, index1, index2;
Int64 RH, LH, LL, xl64, result;
x++;
// normalize input
iexpon = 15;
while ((x & 0x18000) == 0) { x <<= 1; iexpon--; }
index1 = (int) ((x >> 8) << 1);
// RH ~ 2^56/index1
RH = __RH_LH_tbl[index1 - 256];
// LH ~ 2^48 * log2(index1/256)
LH = __RH_LH_tbl[index1 + 1 - 256];
// RH*x ~ 2^48 * (2^15 + xf), xf<2^8
xl64 = x * RH;
xl64 >>= 48;
x1 = (uint) xl64;
result = iexpon;
result <<= (12 + 32);
index2 = (int) (x1 & 0xff);
// LL ~ 2^48*log2(1.0+index2/2^15)
LL = __LL_tbl[index2];
LH = LH + LL;
LH >>= (48 - 12 - 32);
result += LH;
return result;
}
// RH_LH_tbl[2*k] = 2^48/(1.0+k/128.0)
// RH_LH_tbl[2*k+1] = 2^48*log2(1.0+k/128.0)
private static Int64[] __RH_LH_tbl =
new Int64[128 * 2 + 2]
{
0x0001000000000000L, 0x0000000000000000L, 0x0000fe03f80fe040L, 0x000002dfca16dde1L,
0x0000fc0fc0fc0fc1L, 0x000005b9e5a170b4L, 0x0000fa232cf25214L, 0x0000088e68ea899aL,
0x0000f83e0f83e0f9L, 0x00000b5d69bac77eL, 0x0000f6603d980f67L, 0x00000e26fd5c8555L,
0x0000f4898d5f85bcL, 0x000010eb389fa29fL, 0x0000f2b9d6480f2cL, 0x000013aa2fdd27f1L,
0x0000f0f0f0f0f0f1L, 0x00001663f6fac913L, 0x0000ef2eb71fc435L, 0x00001918a16e4633L,
0x0000ed7303b5cc0fL, 0x00001bc84240adabL, 0x0000ebbdb2a5c162L, 0x00001e72ec117fa5L,
0x0000ea0ea0ea0ea1L, 0x00002118b119b4f3L, 0x0000e865ac7b7604L, 0x000023b9a32eaa56L,
0x0000e6c2b4481cd9L, 0x00002655d3c4f15cL, 0x0000e525982af70dL, 0x000028ed53f307eeL,
0x0000e38e38e38e39L, 0x00002b803473f7adL, 0x0000e1fc780e1fc8L, 0x00002e0e85a9de04L,
0x0000e070381c0e08L, 0x0000309857a05e07L, 0x0000dee95c4ca038L, 0x0000331dba0efce1L,
0x0000dd67c8a60dd7L, 0x0000359ebc5b69d9L, 0x0000dbeb61eed19dL, 0x0000381b6d9bb29bL,
0x0000da740da740dbL, 0x00003a93dc9864b2L, 0x0000d901b2036407L, 0x00003d0817ce9cd4L,
0x0000d79435e50d7aL, 0x00003f782d7204d0L, 0x0000d62b80d62b81L, 0x000041e42b6ec0c0L,
0x0000d4c77b03531eL, 0x0000444c1f6b4c2dL, 0x0000d3680d3680d4L, 0x000046b016ca47c1L,
0x0000d20d20d20d21L, 0x000049101eac381cL, 0x0000d0b69fcbd259L, 0x00004b6c43f1366aL,
0x0000cf6474a8819fL, 0x00004dc4933a9337L, 0x0000ce168a772509L, 0x0000501918ec6c11L,
0x0000cccccccccccdL, 0x00005269e12f346eL, 0x0000cb8727c065c4L, 0x000054b6f7f1325aL,
0x0000ca4587e6b750L, 0x0000570068e7ef5aL, 0x0000c907da4e8712L, 0x000059463f919deeL,
0x0000c7ce0c7ce0c8L, 0x00005b8887367433L, 0x0000c6980c6980c7L, 0x00005dc74ae9fbecL,
0x0000c565c87b5f9eL, 0x00006002958c5871L, 0x0000c4372f855d83L, 0x0000623a71cb82c8L,
0x0000c30c30c30c31L, 0x0000646eea247c5cL, 0x0000c1e4bbd595f7L, 0x000066a008e4788cL,
0x0000c0c0c0c0c0c1L, 0x000068cdd829fd81L, 0x0000bfa02fe80bfbL, 0x00006af861e5fc7dL,
0x0000be82fa0be830L, 0x00006d1fafdce20aL, 0x0000bd6910470767L, 0x00006f43cba79e40L,
0x0000bc52640bc527L, 0x00007164beb4a56dL, 0x0000bb3ee721a54eL, 0x000073829248e961L,
0x0000ba2e8ba2e8bbL, 0x0000759d4f80cba8L, 0x0000b92143fa36f6L, 0x000077b4ff5108d9L,
0x0000b81702e05c0cL, 0x000079c9aa879d53L, 0x0000b70fbb5a19bfL, 0x00007bdb59cca388L,
0x0000b60b60b60b61L, 0x00007dea15a32c1bL, 0x0000b509e68a9b95L, 0x00007ff5e66a0ffeL,
0x0000b40b40b40b41L, 0x000081fed45cbccbL, 0x0000b30f63528918L, 0x00008404e793fb81L,
0x0000b21642c8590cL, 0x000086082806b1d5L, 0x0000b11fd3b80b12L, 0x000088089d8a9e47L,
0x0000b02c0b02c0b1L, 0x00008a064fd50f2aL, 0x0000af3addc680b0L, 0x00008c01467b94bbL,
0x0000ae4c415c9883L, 0x00008df988f4ae80L, 0x0000ad602b580ad7L, 0x00008fef1e987409L,
0x0000ac7691840ac8L, 0x000091e20ea1393eL, 0x0000ab8f69e2835aL, 0x000093d2602c2e5fL,
0x0000aaaaaaaaaaabL, 0x000095c01a39fbd6L, 0x0000a9c84a47a080L, 0x000097ab43af59f9L,
0x0000a8e83f5717c1L, 0x00009993e355a4e5L, 0x0000a80a80a80a81L, 0x00009b79ffdb6c8bL,
0x0000a72f0539782aL, 0x00009d5d9fd5010bL, 0x0000a655c4392d7cL, 0x00009f3ec9bcfb80L,
0x0000a57eb50295fbL, 0x0000a11d83f4c355L, 0x0000a4a9cf1d9684L, 0x0000a2f9d4c51039L,
0x0000a3d70a3d70a4L, 0x0000a4d3c25e68dcL, 0x0000a3065e3fae7dL, 0x0000a6ab52d99e76L,
0x0000a237c32b16d0L, 0x0000a8808c384547L, 0x0000a16b312ea8fdL, 0x0000aa5374652a1cL,
0x0000a0a0a0a0a0a1L, 0x0000ac241134c4e9L, 0x00009fd809fd80a0L, 0x0000adf26865a8a1L,
0x00009f1165e72549L, 0x0000afbe7fa0f04dL, 0x00009e4cad23dd60L, 0x0000b1885c7aa982L,
0x00009d89d89d89d9L, 0x0000b35004723c46L, 0x00009cc8e160c3fcL, 0x0000b5157cf2d078L,
0x00009c09c09c09c1L, 0x0000b6d8cb53b0caL, 0x00009b4c6f9ef03bL, 0x0000b899f4d8ab63L,
0x00009a90e7d95bc7L, 0x0000ba58feb2703aL, 0x000099d722dabde6L, 0x0000bc15edfeed32L,
0x0000991f1a515886L, 0x0000bdd0c7c9a817L, 0x00009868c809868dL, 0x0000bf89910c1678L,
0x000097b425ed097cL, 0x0000c1404eadf383L, 0x000097012e025c05L, 0x0000c2f5058593d9L,
0x0000964fda6c0965L, 0x0000c4a7ba58377cL, 0x000095a02568095bL, 0x0000c65871da59ddL,
0x000094f2094f2095L, 0x0000c80730b00016L, 0x0000944580944581L, 0x0000c9b3fb6d0559L,
0x0000939a85c4093aL, 0x0000cb5ed69565afL, 0x000092f113840498L, 0x0000cd07c69d8702L,
0x0000924924924925L, 0x0000ceaecfea8085L, 0x000091a2b3c4d5e7L, 0x0000d053f6d26089L,
0x000090fdbc090fdcL, 0x0000d1f73f9c70c0L, 0x0000905a38633e07L, 0x0000d398ae817906L,
0x00008fb823ee08fcL, 0x0000d53847ac00a6L, 0x00008f1779d9fdc4L, 0x0000d6d60f388e41L,
0x00008e78356d1409L, 0x0000d8720935e643L, 0x00008dda5202376aL, 0x0000da0c39a54804L,
0x00008d3dcb08d3ddL, 0x0000dba4a47aa996L, 0x00008ca29c046515L, 0x0000dd3b4d9cf24bL,
0x00008c08c08c08c1L, 0x0000ded038e633f3L, 0x00008b70344a139cL, 0x0000e0636a23e2eeL,
0x00008ad8f2fba939L, 0x0000e1f4e5170d02L, 0x00008a42f870566aL, 0x0000e384ad748f0eL,
0x000089ae4089ae41L, 0x0000e512c6e54998L, 0x0000891ac73ae982L, 0x0000e69f35065448L,
0x0000888888888889L, 0x0000e829fb693044L, 0x000087f78087f781L, 0x0000e9b31d93f98eL,
0x00008767ab5f34e5L, 0x0000eb3a9f019750L, 0x000086d905447a35L, 0x0000ecc08321eb30L,
0x0000864b8a7de6d2L, 0x0000ee44cd59ffabL, 0x000085bf37612cefL, 0x0000efc781043579L,
0x0000853408534086L, 0x0000f148a170700aL, 0x000084a9f9c8084bL, 0x0000f2c831e44116L,
0x0000842108421085L, 0x0000f446359b1353L, 0x0000839930523fbfL, 0x0000f5c2afc65447L,
0x000083126e978d50L, 0x0000f73da38d9d4aL, 0x0000828cbfbeb9a1L, 0x0000f8b7140edbb1L,
0x0000820820820821L, 0x0000fa2f045e7832L, 0x000081848da8faf1L, 0x0000fba577877d7dL,
0x0000810204081021L, 0x0000fd1a708bbe11L, 0x0000808080808081L, 0x0000fe8df263f957L,
0x0000800000000000L, 0x0000ffff00000000L,
};
// LL_tbl[k] = 2^48*log2(1.0+k/2^15);
private static Int64[] __LL_tbl =
new Int64[256]
{
0x0000000000000000L, 0x00000002e2a60a00L, 0x000000070cb64ec5L, 0x00000009ef50ce67L,
0x0000000cd1e588fdL, 0x0000000fb4747e9cL, 0x0000001296fdaf5eL, 0x0000001579811b58L,
0x000000185bfec2a1L, 0x0000001b3e76a552L, 0x0000001e20e8c380L, 0x0000002103551d43L,
0x00000023e5bbb2b2L, 0x00000026c81c83e4L, 0x00000029aa7790f0L, 0x0000002c8cccd9edL,
0x0000002f6f1c5ef2L, 0x0000003251662017L, 0x0000003533aa1d71L, 0x0000003815e8571aL,
0x0000003af820cd26L, 0x0000003dda537faeL, 0x00000040bc806ec8L, 0x000000439ea79a8cL,
0x0000004680c90310L, 0x0000004962e4a86cL, 0x0000004c44fa8ab6L, 0x0000004f270aaa06L,
0x0000005209150672L, 0x00000054eb19a013L, 0x00000057cd1876fdL, 0x0000005aaf118b4aL,
0x0000005d9104dd0fL, 0x0000006072f26c64L, 0x0000006354da3960L, 0x0000006636bc441aL,
0x0000006918988ca8L, 0x0000006bfa6f1322L, 0x0000006edc3fd79fL, 0x00000071be0ada35L,
0x000000749fd01afdL, 0x00000077818f9a0cL, 0x0000007a6349577aL, 0x0000007d44fd535eL,
0x0000008026ab8dceL, 0x00000083085406e3L, 0x00000085e9f6beb2L, 0x00000088cb93b552L,
0x0000008bad2aeadcL, 0x0000008e8ebc5f65L, 0x0000009170481305L, 0x0000009451ce05d3L,
0x00000097334e37e5L, 0x0000009a14c8a953L, 0x0000009cf63d5a33L, 0x0000009fd7ac4a9dL,
0x000000a2b07f3458L, 0x000000a59a78ea6aL, 0x000000a87bd699fbL, 0x000000ab5d2e8970L,
0x000000ae3e80b8e3L, 0x000000b11fcd2869L, 0x000000b40113d818L, 0x000000b6e254c80aL,
0x000000b9c38ff853L, 0x000000bca4c5690cL, 0x000000bf85f51a4aL, 0x000000c2671f0c26L,
0x000000c548433eb6L, 0x000000c82961b211L, 0x000000cb0a7a664dL, 0x000000cdeb8d5b82L,
0x000000d0cc9a91c8L, 0x000000d3ada20933L, 0x000000d68ea3c1ddL, 0x000000d96f9fbbdbL,
0x000000dc5095f744L, 0x000000df31867430L, 0x000000e2127132b5L, 0x000000e4f35632eaL,
0x000000e7d43574e6L, 0x000000eab50ef8c1L, 0x000000ed95e2be90L, 0x000000f076b0c66cL,
0x000000f35779106aL, 0x000000f6383b9ca2L, 0x000000f918f86b2aL, 0x000000fbf9af7c1aL,
0x000000feda60cf88L, 0x00000101bb0c658cL, 0x000001049bb23e3cL, 0x000001077c5259afL,
0x0000010a5cecb7fcL, 0x0000010d3d81593aL, 0x000001101e103d7fL, 0x00000112fe9964e4L,
0x00000115df1ccf7eL, 0x00000118bf9a7d64L, 0x0000011ba0126eadL, 0x0000011e8084a371L,
0x0000012160f11bc6L, 0x000001244157d7c3L, 0x0000012721b8d77fL, 0x0000012a02141b10L,
0x0000012ce269a28eL, 0x0000012fc2b96e0fL, 0x00000132a3037daaL, 0x000001358347d177L,
0x000001386386698cL, 0x0000013b43bf45ffL, 0x0000013e23f266e9L, 0x00000141041fcc5eL,
0x00000143e4477678L, 0x00000146c469654bL, 0x00000149a48598f0L, 0x0000014c849c117cL,
0x0000014f64accf08L, 0x0000015244b7d1a9L, 0x0000015524bd1976L, 0x0000015804bca687L,
0x0000015ae4b678f2L, 0x0000015dc4aa90ceL, 0x00000160a498ee31L, 0x0000016384819134L,
0x00000166646479ecL, 0x000001694441a870L, 0x0000016c24191cd7L, 0x0000016df6ca19bdL,
0x00000171e3b6d7aaL, 0x00000174c37d1e44L, 0x00000177a33dab1cL, 0x0000017a82f87e49L,
0x0000017d62ad97e2L, 0x00000180425cf7feL, 0x00000182b07f3458L, 0x0000018601aa8c19L,
0x00000188e148c046L, 0x0000018bc0e13b52L, 0x0000018ea073fd52L, 0x000001918001065dL,
0x000001945f88568bL, 0x000001973f09edf2L, 0x0000019a1e85ccaaL, 0x0000019cfdfbf2c8L,
0x0000019fdd6c6063L, 0x000001a2bcd71593L, 0x000001a59c3c126eL, 0x000001a87b9b570bL,
0x000001ab5af4e380L, 0x000001ae3a48b7e5L, 0x000001b11996d450L, 0x000001b3f8df38d9L,
0x000001b6d821e595L, 0x000001b9b75eda9bL, 0x000001bc96961803L, 0x000001bf75c79de3L,
0x000001c254f36c51L, 0x000001c534198365L, 0x000001c81339e336L, 0x000001caf2548bd9L,
0x000001cdd1697d67L, 0x000001d0b078b7f5L, 0x000001d38f823b9aL, 0x000001d66e86086dL,
0x000001d94d841e86L, 0x000001dc2c7c7df9L, 0x000001df0b6f26dfL, 0x000001e1ea5c194eL,
0x000001e4c943555dL, 0x000001e7a824db23L, 0x000001ea8700aab5L, 0x000001ed65d6c42bL,
0x000001f044a7279dL, 0x000001f32371d51fL, 0x000001f60236cccaL, 0x000001f8e0f60eb3L,
0x000001fbbfaf9af3L, 0x000001fe9e63719eL, 0x000002017d1192ccL, 0x000002045bb9fe94L,
0x000002073a5cb50dL, 0x00000209c06e6212L, 0x0000020cf791026aL, 0x0000020fd622997cL,
0x00000212b07f3458L, 0x000002159334a8d8L, 0x0000021871b52150L, 0x0000021b502fe517L,
0x0000021d6a73a78fL, 0x000002210d144eeeL, 0x00000223eb7df52cL, 0x00000226c9e1e713L,
0x00000229a84024bbL, 0x0000022c23679b4eL, 0x0000022f64eb83a8L, 0x000002324338a51bL,
0x00000235218012a9L, 0x00000237ffc1cc69L, 0x0000023a2c3b0ea4L, 0x0000023d13ee805bL,
0x0000024035e9221fL, 0x00000243788faf25L, 0x0000024656b4e735L, 0x00000247ed646bfeL,
0x0000024c12ee3d98L, 0x0000024ef1025c1aL, 0x00000251cf10c799L, 0x0000025492644d65L,
0x000002578b1c85eeL, 0x0000025a6919d8f0L, 0x0000025d13ee805bL, 0x0000026025036716L,
0x0000026296453882L, 0x00000265e0d62b53L, 0x00000268beb701f3L, 0x0000026b9c92265eL,
0x0000026d32f798a9L, 0x00000271583758ebL, 0x000002743601673bL, 0x0000027713c5c3b0L,
0x00000279f1846e5fL, 0x0000027ccf3d6761L, 0x0000027e6580aecbL, 0x000002828a9e44b3L,
0x0000028568462932L, 0x00000287bdbf5255L, 0x0000028b2384de4aL, 0x0000028d13ee805bL,
0x0000029035e9221fL, 0x0000029296453882L, 0x0000029699bdfb61L, 0x0000029902a37aabL,
0x0000029c54b864c9L, 0x0000029deabd1083L, 0x000002a20f9c0bb5L, 0x000002a4c7605d61L,
0x000002a7bdbf5255L, 0x000002a96056dafcL, 0x000002ac3daf14efL, 0x000002af1b019ecaL,
0x000002b296453882L, 0x000002b5d022d80fL, 0x000002b8fa471cb3L, 0x000002ba9012e713L,
0x000002bd6d4901ccL, 0x000002c04a796cf6L, 0x000002c327a428a6L, 0x000002c61a5e8f4cL,
0x000002c8e1e891f6L, 0x000002cbbf023fc2L, 0x000002ce9c163e6eL, 0x000002d179248e13L,
0x000002d4562d2ec6L, 0x000002d73330209dL, 0x000002da102d63b0L, 0x000002dced24f814L,
};
}
}