rolling_hash.h

Go to the documentation of this file.

/*
 * Copyright 2010 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http:///www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef PAGESPEED_KERNEL_BASE_ROLLING_HASH_H_
#define PAGESPEED_KERNEL_BASE_ROLLING_HASH_H_

#include <cstddef>
#include "base/logging.h"
#include "pagespeed/kernel/base/basictypes.h"

namespace net_instaweb {


extern const uint64 kRollingHashCharTable[256];

uint64 RollingHash(const char* buf, size_t start, size_t n);

inline uint64 NextRollingHash(
    const char* buf, size_t start, size_t n, uint64 prev) {
  CHECK_LT(static_cast<size_t>(0), start);
  uint64 start_hash =
      kRollingHashCharTable[static_cast<uint8>(buf[start - 1])];
  uint64 end_hash =
      kRollingHashCharTable[static_cast<uint8>(buf[start - 1 + n])];
  uint64 prev_rot1 = (prev << 1) | (prev >> 63); 
  uint64 start_hash_rotn;
  size_t shift = n % 64;
  if (shift == 0) {
    start_hash_rotn = start_hash;
  } else {
    start_hash_rotn = (start_hash << shift) | (start_hash >> (64 - shift));
  }
  return (start_hash_rotn ^ prev_rot1 ^ end_hash);
}
}  

#endif