interleave_test.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  import "testing"
    18  
    19  func TestInterleaveUint32(t *testing.T) {
    20  	x, y := uint32(13356), uint32(1073728367)
    21  	gotX, gotY := deinterleaveUint32(interleaveUint32(x, y))
    22  	if gotX != x || gotY != y {
    23  		t.Errorf("deinterleave after interleave = %d, %d; want %d, %d", gotX, gotY, x, y)
    24  	}
    25  }
    26  
    27  func referenceBitInterleave(x, y uint32) uint64 {
    28  	var ret uint64
    29  	for i := uint(0); i < 32; i++ {
    30  		ret |= uint64((x>>i)&1) << (i * 2)
    31  		ret |= uint64((y>>i)&1) << (i*2 + 1)
    32  	}
    33  	return ret
    34  }
    35  
    36  func TestInterleaveUint32AgainstReference(t *testing.T) {
    37  	// TODO(nsch): Add the remaining parts of the tests later. (the various other primes and bit AND-ings.)
    38  	for i := 0; i < 100000; i++ {
    39  		wantEven := uint32(i) * 14233781
    40  		wantOdd := uint32(i) * 18400439
    41  
    42  		gotInter := interleaveUint32(wantEven, wantOdd)
    43  		wantInter := referenceBitInterleave(wantEven, wantOdd)
    44  		if gotInter != wantInter {
    45  			t.Fatalf("interleaveUint32(%d, %d) = %d, want %d", wantEven, wantOdd, gotInter, wantInter)
    46  		}
    47  
    48  		gotEven, gotOdd := deinterleaveUint32(gotInter)
    49  		if gotEven != wantEven {
    50  			t.Fatalf("interleave: %d vs %d", gotEven, wantEven)
    51  		}
    52  		if gotOdd != wantOdd {
    53  			t.Fatalf("interleave: %d vs %d", gotOdd, wantOdd)
    54  		}
    55  	}
    56  }
    57  
    58  func TestInterleaveBasics(t *testing.T) {
    59  	tests := []struct {
    60  		x, y uint32
    61  		want uint64
    62  	}{
    63  		// Interleave zeroes.
    64  		{0, 0, 0},
    65  		// Interleave ones.
    66  		{1, 0, 1}, {0, 1, 2}, {1, 1, 3},
    67  		// Interleave all bits.
    68  		{0xffffffff, 0, 0x5555555555555555},
    69  		{0, 0xffffffff, 0xaaaaaaaaaaaaaaaa},
    70  		{0xffffffff, 0xffffffff, 0xffffffffffffffff},
    71  	}
    72  	for _, tt := range tests {
    73  		if got := interleaveUint32(tt.x, tt.y); got != tt.want {
    74  			t.Errorf("interleaveUint32(%d, %d) = %d, want %d", tt.x, tt.y, got, tt.want)
    75  		}
    76  	}
    77  }
    78
View as plain text