interleave.go (6155B)
1 // Copyright 2017 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package s2 16 17 /* 18 The lookup table below can convert a sequence of interleaved 8 bits into 19 non-interleaved 4 bits. The table can convert both odd and even bits at the 20 same time, and lut[x & 0x55] converts the even bits (bits 0, 2, 4 and 6), 21 while lut[x & 0xaa] converts the odd bits (bits 1, 3, 5 and 7). 22 23 The lookup table below was generated using the following python code: 24 25 def deinterleave(bits): 26 if bits == 0: return 0 27 if bits < 4: return 1 28 return deinterleave(bits / 4) * 2 + deinterleave(bits & 3) 29 30 for i in range(256): print "0x%x," % deinterleave(i), 31 */ 32 var deinterleaveLookup = [256]uint32{ 33 0x0, 0x1, 0x1, 0x1, 0x2, 0x3, 0x3, 0x3, 34 0x2, 0x3, 0x3, 0x3, 0x2, 0x3, 0x3, 0x3, 35 0x4, 0x5, 0x5, 0x5, 0x6, 0x7, 0x7, 0x7, 36 0x6, 0x7, 0x7, 0x7, 0x6, 0x7, 0x7, 0x7, 37 0x4, 0x5, 0x5, 0x5, 0x6, 0x7, 0x7, 0x7, 38 0x6, 0x7, 0x7, 0x7, 0x6, 0x7, 0x7, 0x7, 39 0x4, 0x5, 0x5, 0x5, 0x6, 0x7, 0x7, 0x7, 40 0x6, 0x7, 0x7, 0x7, 0x6, 0x7, 0x7, 0x7, 41 42 0x8, 0x9, 0x9, 0x9, 0xa, 0xb, 0xb, 0xb, 43 0xa, 0xb, 0xb, 0xb, 0xa, 0xb, 0xb, 0xb, 44 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 45 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 46 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 47 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 48 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 49 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 50 51 0x8, 0x9, 0x9, 0x9, 0xa, 0xb, 0xb, 0xb, 52 0xa, 0xb, 0xb, 0xb, 0xa, 0xb, 0xb, 0xb, 53 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 54 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 55 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 56 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 57 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 58 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 59 60 0x8, 0x9, 0x9, 0x9, 0xa, 0xb, 0xb, 0xb, 61 0xa, 0xb, 0xb, 0xb, 0xa, 0xb, 0xb, 0xb, 62 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 63 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 64 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 65 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 66 0xc, 0xd, 0xd, 0xd, 0xe, 0xf, 0xf, 0xf, 67 0xe, 0xf, 0xf, 0xf, 0xe, 0xf, 0xf, 0xf, 68 } 69 70 // deinterleaveUint32 decodes the interleaved values. 71 func deinterleaveUint32(code uint64) (uint32, uint32) { 72 x := (deinterleaveLookup[code&0x55]) | 73 (deinterleaveLookup[(code>>8)&0x55] << 4) | 74 (deinterleaveLookup[(code>>16)&0x55] << 8) | 75 (deinterleaveLookup[(code>>24)&0x55] << 12) | 76 (deinterleaveLookup[(code>>32)&0x55] << 16) | 77 (deinterleaveLookup[(code>>40)&0x55] << 20) | 78 (deinterleaveLookup[(code>>48)&0x55] << 24) | 79 (deinterleaveLookup[(code>>56)&0x55] << 28) 80 y := (deinterleaveLookup[code&0xaa]) | 81 (deinterleaveLookup[(code>>8)&0xaa] << 4) | 82 (deinterleaveLookup[(code>>16)&0xaa] << 8) | 83 (deinterleaveLookup[(code>>24)&0xaa] << 12) | 84 (deinterleaveLookup[(code>>32)&0xaa] << 16) | 85 (deinterleaveLookup[(code>>40)&0xaa] << 20) | 86 (deinterleaveLookup[(code>>48)&0xaa] << 24) | 87 (deinterleaveLookup[(code>>56)&0xaa] << 28) 88 return x, y 89 } 90 91 var interleaveLookup = [256]uint64{ 92 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 93 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 94 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 95 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 96 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 97 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 98 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 99 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, 100 101 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 102 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, 103 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 104 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 105 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 106 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 107 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, 108 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 109 110 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, 111 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 112 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 113 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 114 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 115 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, 116 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 117 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, 118 119 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 120 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 121 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 122 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 123 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, 124 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 125 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, 126 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555, 127 } 128 129 // interleaveUint32 interleaves the given arguments into the return value. 130 // 131 // The 0-bit in val0 will be the 0-bit in the return value. 132 // The 0-bit in val1 will be the 1-bit in the return value. 133 // The 1-bit of val0 will be the 2-bit in the return value, and so on. 134 func interleaveUint32(x, y uint32) uint64 { 135 return (interleaveLookup[x&0xff]) | 136 (interleaveLookup[(x>>8)&0xff] << 16) | 137 (interleaveLookup[(x>>16)&0xff] << 32) | 138 (interleaveLookup[x>>24] << 48) | 139 (interleaveLookup[y&0xff] << 1) | 140 (interleaveLookup[(y>>8)&0xff] << 17) | 141 (interleaveLookup[(y>>16)&0xff] << 33) | 142 (interleaveLookup[y>>24] << 49) 143 }