interleave.go

Documentation: github.com/golang/geo/s2

     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  }
   144
View as plain text