redis-3.2.9.tar.gz

/*
 * Copyright （c） 2013-2014 yinqiwen 
 * Copyright （c） 2014 Matt Stancliff .
 * Copyright （c） 2015-2016 Salvatore Sanfilippo .
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms with or without
 * modification are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice
 *    this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright
 *    notice this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *  * Neither the name of Redis nor the names of its contributors may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS“
 * AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT INDIRECT INCIDENTAL SPECIAL EXEMPLARY OR
 * CONSEQUENTIAL DAMAGES （INCLUDING BUT NOT LIMITED TO PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE DATA OR PROFITS; OR BUSINESS
 * INTERRUPTION） HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY WHETHER IN
 * CONTRACT STRICT LIABILITY OR TORT （INCLUDING NEGLIGENCE OR OTHERWISE）
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */
#include “geohash.h“

/**
 * Hashing works like this:
 * Divide the world into 4 buckets.  Label each one as such:
 *  -----------------
 *  |       |       |
 *  |       |       |
 *  | 01   | 11   |
 *  -----------------
 *  |       |       |
 *  |       |       |
 *  | 00   | 10   |
 *  -----------------
 */

/* Interleave lower bits of x and y so the bits of x
 * are in the even positions and bits from y in the odd;
 * x and y must initially be less than 2**32 （65536）.
 * From:  https://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
 */
static inline uint64_t interleave64（uint32_t xlo uint32_t ylo） {
    static const uint64_t B[] = {0x5555555555555555ULL 0x3333333333333333ULL
                                 0x0F0F0F0F0F0F0F0FULL 0x00FF00FF00FF00FFULL
                                 0x0000FFFF0000FFFFULL};
    static const unsigned int S[] = {1 2 4 8 16};

    uint64_t x = xlo;
    uint64_t y = ylo;

    x = （x | （x << S[4]）） & B[4];
    y = （y | （y << S[4]）） & B[4];

    x = （x | （x << S[3]）） & B[3];
    y = （y | （y << S[3]）） & B[3];

    x = （x | （x << S[2]）） & B[2];
    y = （y | （y << S[2]）） & B[2];

    x = （x | （x << S[1]）） & B[1];
    y = （y | （y << S[1]）） & B[1];

    x = （x | （x << S[0]）） & B[0];
    y = （y | （y << S[0]）） & B[0];