Initial checkin.

git-svn-id: https://leveldb.googlecode.com/svn/trunk@2 62dab493-f737-651d-591e-8d6aee1b9529

12 files changed, 1069 insertions, 0 deletions

diff --git a/port/README b/port/README
new file mode 100644
index 0000000..422563e
--- /dev/null
+++ b/port/README
@@ -0,0 +1,10 @@
+This directory contains interfaces and implementations that isolate the
+rest of the package from platform details.
+
+Code in the rest of the package includes "port.h" from this directory.
+"port.h" in turn includes a platform specific "port_<platform>.h" file
+that provides the platform specific implementation.
+
+See port_posix.h for an example of what must be provided in a platform
+specific header file.
+
diff --git a/port/port.h b/port/port.h
new file mode 100644
index 0000000..816826b
--- /dev/null
+++ b/port/port.h
@@ -0,0 +1,21 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#ifndef STORAGE_LEVELDB_PORT_PORT_H_
+#define STORAGE_LEVELDB_PORT_PORT_H_
+
+#include <string.h>
+
+// Include the appropriate platform specific file below.  If you are
+// porting to a new platform, see "port_example.h" for documentation
+// of what the new port_<platform>.h file must provide.
+#if defined(LEVELDB_PLATFORM_POSIX)
+#  include "port/port_posix.h"
+#elif defined(LEVELDB_PLATFORM_CHROMIUM)
+#  include "port/port_chromium.h"
+#elif defined(LEVELDB_PLATFORM_ANDROID)
+#  include "port/port_android.h"
+#endif
+
+#endif  // STORAGE_LEVELDB_PORT_PORT_H_
diff --git a/port/port_android.cc b/port/port_android.cc
new file mode 100644
index 0000000..8a74111
--- /dev/null
+++ b/port/port_android.cc
@@ -0,0 +1,65 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#include "port/port_android.h"
+
+#include <cstdlib>
+
+extern "C" {
+size_t fread_unlocked(void *a, size_t b, size_t c, FILE *d) {
+  return fread(a, b, c, d);
+}
+
+size_t fwrite_unlocked(const void *a, size_t b, size_t c, FILE *d) {
+  return fwrite(a, b, c, d);
+}
+
+int fflush_unlocked(FILE *f) {
+  return fflush(f);
+}
+
+int fdatasync(int fd) {
+  return fsync(fd);
+}
+}
+
+// TODO(gabor): This is copied from port_posix.cc - not sure if I should do this?
+namespace leveldb {
+namespace port {
+
+static void PthreadCall(const char* label, int result) {
+  if (result != 0) {
+    fprintf(stderr, "pthread %s: %s\n", label, strerror(result));
+    abort();
+  }
+}
+
+Mutex::Mutex() { PthreadCall("init mutex", pthread_mutex_init(&mu_, NULL)); }
+Mutex::~Mutex() { PthreadCall("destroy mutex", pthread_mutex_destroy(&mu_)); }
+void Mutex::Lock() { PthreadCall("lock", pthread_mutex_lock(&mu_)); }
+void Mutex::Unlock() { PthreadCall("unlock", pthread_mutex_unlock(&mu_)); }
+
+CondVar::CondVar(Mutex* mu)
+    : mu_(mu) {
+  PthreadCall("init cv", pthread_cond_init(&cv_, NULL));
+}
+
+CondVar::~CondVar() { 
+  PthreadCall("destroy cv", pthread_cond_destroy(&cv_));
+}
+
+void CondVar::Wait() {
+  PthreadCall("wait", pthread_cond_wait(&cv_, &mu_->mu_));
+}
+
+void CondVar::Signal(){
+  PthreadCall("signal", pthread_cond_signal(&cv_));
+}
+
+void CondVar::SignalAll() {
+  PthreadCall("broadcast", pthread_cond_broadcast(&cv_));
+}
+
+}
+}
diff --git a/port/port_android.h b/port/port_android.h
new file mode 100644
index 0000000..2770a0c
--- /dev/null
+++ b/port/port_android.h
@@ -0,0 +1,131 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+//
+// See port_example.h for documentation for the following types/functions.
+
+#ifndef STORAGE_LEVELDB_PORT_PORT_ANDROID_H_
+#define STORAGE_LEVELDB_PORT_PORT_ANDROID_H_
+
+#include <endian.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <sha1.h>
+#include <cstdatomic>
+#include <string>
+#include <cctype>
+
+extern "C" {
+  size_t fread_unlocked(void *a, size_t b, size_t c, FILE *d);
+  size_t fwrite_unlocked(const void *a, size_t b, size_t c, FILE *d);
+  int fflush_unlocked(FILE *f);
+  int fdatasync (int fd);
+}
+
+namespace leveldb {
+namespace port {
+
+static const bool kLittleEndian = __BYTE_ORDER == __LITTLE_ENDIAN;
+
+class CondVar;
+
+class Mutex {
+ public:
+  Mutex();
+  ~Mutex();
+
+  void Lock();
+  void Unlock();
+  void AssertHeld() {
+    //TODO(gabor): How can I implement this?
+  }
+
+ private:
+  friend class CondVar;
+  pthread_mutex_t mu_;
+
+  // No copying
+  Mutex(const Mutex&);
+  void operator=(const Mutex&);
+};
+
+class CondVar {
+ public:
+  explicit CondVar(Mutex* mu);
+  ~CondVar();
+  void Wait();
+  void Signal();
+  void SignalAll();
+ private:
+  Mutex* mu_;
+  pthread_cond_t cv_;
+};
+
+// Storage for a lock-free pointer
+class AtomicPointer {
+ private:
+  std::atomic<void*> rep_;
+ public:
+  AtomicPointer() { }
+  explicit AtomicPointer(void* v) : rep_(v) { }
+  inline void* Acquire_Load() const {
+    return rep_.load(std::memory_order_acquire);
+  }
+  inline void Release_Store(void* v) {
+    rep_.store(v, std::memory_order_release);
+  }
+  inline void* NoBarrier_Load() const {
+    return rep_.load(std::memory_order_relaxed);
+  }
+  inline void NoBarrier_Store(void* v) {
+    rep_.store(v, std::memory_order_relaxed);
+  }
+};
+
+/**
+ * TODO(gabor): Implement actual compress
+ *     This is a hack - it just copies input to output.
+ *     No actual compression occurs.
+ */
+inline void Lightweight_Compress(
+    const char* input,
+    size_t input_length,
+    std::string* output) {
+  output->copy((char*)input,0,input_length);
+}
+
+/**
+ * TODO(gabor): Implement actual compress
+ *     This is a hack - it just copies input to output.
+ *     No actual uncompression occurs.
+ */
+inline bool Lightweight_Uncompress(
+    const char* input_data,
+    size_t input_length,
+    std::string* output) {
+  output->copy((char*)input_data,0,input_length);
+  return (bool)1;
+}
+
+inline void SHA1_Hash(const char* data, size_t len, char* hash_array) {
+  SHA1_CTX sha1_ctx;
+  SHA1Init(&sha1_ctx);
+  SHA1Update(&sha1_ctx, (const u_char*)data, len);
+  SHA1Final((u_char*)hash_array, &sha1_ctx);
+}
+
+inline uint64_t ThreadIdentifier() {
+  pthread_t tid = pthread_self();
+  uint64_t r = 0;
+  memcpy(&r, &tid, sizeof(r) < sizeof(tid) ? sizeof(r) : sizeof(tid));
+  return r;
+}
+
+inline bool GetHeapProfile(void (*func)(void*, const char*, int), void* arg) {
+  return false;
+}
+
+}
+}
+
+#endif  // STORAGE_LEVELDB_PORT_PORT_ANDROID_H_
diff --git a/port/port_chromium.cc b/port/port_chromium.cc
new file mode 100644
index 0000000..c022ec4
--- /dev/null
+++ b/port/port_chromium.cc
@@ -0,0 +1,83 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#include "port/port_chromium.h"
+
+#include "util/logging.h"
+
+#if defined(USE_SNAPPY)
+#  include "third_party/snappy/src/snappy.h"
+#  include "third_party/snappy/src/snappy-stubs.h"
+#endif
+
+namespace leveldb {
+namespace port {
+
+Mutex::Mutex() {
+}
+
+Mutex::~Mutex() {
+}
+
+void Mutex::Lock() {
+  mu_.Acquire();
+}
+
+void Mutex::Unlock() {
+  mu_.Release();
+}
+
+void Mutex::AssertHeld() {
+  mu_.AssertAcquired();
+}
+
+CondVar::CondVar(Mutex* mu)
+    : cv_(&mu->mu_) {
+}
+
+CondVar::~CondVar() { }
+
+void CondVar::Wait() {
+  cv_.Wait();
+}
+
+void CondVar::Signal(){
+  cv_.Signal();
+}
+
+void CondVar::SignalAll() {
+  cv_.Broadcast();
+}
+
+void Lightweight_Compress(const char* input, size_t input_length,
+                          std::string* output) {
+#if defined(USE_SNAPPY)
+  output->resize(snappy::MaxCompressedLength(input_length));
+  size_t outlen;
+  snappy::RawCompress(snappy::StringPiece(input, input_length),
+                      &(*output)[0], &outlen);
+  output->resize(outlen);
+#else
+  output->assign(input, input_length);
+#endif
+}
+
+bool Lightweight_Uncompress(const char* input_data, size_t input_length,
+                            std::string* output) {
+#if defined(USE_SNAPPY)
+  snappy::StringPiece input(input_data, input_length);
+  size_t ulength;
+  if (!snappy::GetUncompressedLength(input, &ulength)) {
+    return false;
+  }
+  output->resize(ulength);
+  return snappy::RawUncompress(input, &(*output)[0]);
+#else
+  output->assign(input_data, input_length);
+  return true;
+#endif
+}
+
+}
+}
diff --git a/port/port_chromium.h b/port/port_chromium.h
new file mode 100644
index 0000000..b33bdde
--- /dev/null
+++ b/port/port_chromium.h
@@ -0,0 +1,104 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+//
+// See port_example.h for documentation for the following types/functions.
+
+#ifndef STORAGE_LEVELDB_PORT_PORT_CHROMIUM_H_
+#define STORAGE_LEVELDB_PORT_PORT_CHROMIUM_H_
+
+#include <stdint.h>
+#include <string>
+#include <cstring>
+#include "base/atomicops.h"
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/sha1.h"
+#include "base/synchronization/condition_variable.h"
+#include "base/synchronization/lock.h"
+
+// Linux's ThreadIdentifier() needs this.
+#if defined(OS_LINUX)
+#  include <linux/unistd.h>
+#endif
+
+#if defined(OS_WIN)
+#define snprintf _snprintf
+#define va_copy(a, b) do { (a) = (b); } while (0)
+#endif
+
+namespace leveldb {
+namespace port {
+
+// Chromium only supports little endian.
+static const bool kLittleEndian = true;
+
+class Mutex {
+ public:
+  Mutex();
+  ~Mutex();
+  void Lock();
+  void Unlock();
+  void AssertHeld();
+
+ private:
+  base::Lock mu_;
+
+  friend class CondVar;
+  DISALLOW_COPY_AND_ASSIGN(Mutex);
+};
+
+class CondVar {
+ public:
+  explicit CondVar(Mutex* mu);
+  ~CondVar();
+  void Wait();
+  void Signal();
+  void SignalAll();
+
+ private:
+  base::ConditionVariable cv_;
+
+  DISALLOW_COPY_AND_ASSIGN(CondVar);
+};
+
+class AtomicPointer {
+ private:
+  typedef base::subtle::AtomicWord Rep;
+  Rep rep_;
+ public:
+  AtomicPointer() { }
+  explicit AtomicPointer(void* p) : rep_(reinterpret_cast<Rep>(p)) {}
+  inline void* Acquire_Load() const {
+    return reinterpret_cast<void*>(::base::subtle::Acquire_Load(&rep_));
+  }
+  inline void Release_Store(void* v) {
+    ::base::subtle::Release_Store(&rep_, reinterpret_cast<Rep>(v));
+  }
+  inline void* NoBarrier_Load() const {
+    return reinterpret_cast<void*>(::base::subtle::NoBarrier_Load(&rep_));
+  }
+  inline void NoBarrier_Store(void* v) {
+    ::base::subtle::NoBarrier_Store(&rep_, reinterpret_cast<Rep>(v));
+  }
+};
+
+inline void SHA1_Hash(const char* data, size_t len, char* hash_array) {
+  return ::base::SHA1HashBytes(reinterpret_cast<const unsigned char*>(data),
+                               len,
+                               reinterpret_cast<unsigned char*>(hash_array));
+}
+
+void Lightweight_Compress(const char* input, size_t input_length,
+                          std::string* output);
+bool Lightweight_Uncompress(const char* input_data, size_t input_length,
+                            std::string* output);
+
+inline bool GetHeapProfile(void (*func)(void*, const char*, int), void* arg) {
+  return false;
+}
+
+}
+}
+
+#endif  // STORAGE_LEVELDB_PORT_PORT_CHROMIUM_H_
diff --git a/port/port_example.h b/port/port_example.h
new file mode 100644
index 0000000..ee25a01
--- /dev/null
+++ b/port/port_example.h
@@ -0,0 +1,119 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+//
+// This file contains the specification, but not the implementations,
+// of the types/operations/etc. that should be defined by a platform
+// specific port_<platform>.h file.  Use this file as a reference for
+// how to port this package to a new platform.
+
+#ifndef STORAGE_LEVELDB_PORT_PORT_EXAMPLE_H_
+#define STORAGE_LEVELDB_PORT_PORT_EXAMPLE_H_
+
+namespace leveldb {
+namespace port {
+
+// TODO(jorlow): Many of these belong more in the environment class rather than
+//               here. We should try moving them and see if it affects perf.
+
+// The following boolean constant must be true on a little-endian machine
+// and false otherwise.
+static const bool kLittleEndian = true /* or some other expression */;
+
+// ------------------ Threading -------------------
+
+// A Mutex represents an exclusive lock.
+class Mutex {
+ public:
+  Mutex();
+  ~Mutex();
+
+  // Lock the mutex.  Waits until other lockers have exited.
+  // Will deadlock if the mutex is already locked by this thread.
+  void Lock();
+
+  // Unlock the mutex.
+  // REQUIRES: This mutex was locked by this thread.
+  void Unlock();
+
+  // Optionally crash if this thread does not hold this mutex.
+  // The implementation must be fast, especially if NDEBUG is
+  // defined.  The implementation is allowed to skip all checks.
+  void AssertHeld();
+};
+
+class CondVar {
+ public:
+  explicit CondVar(Mutex* mu);
+  ~CondVar();
+
+  // Atomically release *mu and block on this condition variable until
+  // either a call to SignalAll(), or a call to Signal() that picks
+  // this thread to wakeup.
+  // REQUIRES: this thread holds *mu
+  void Wait();
+
+  // If there are some threads waiting, wake up at least one of them.
+  void Signal();
+
+  // Wake up all waiting threads.
+  void SignallAll();
+};
+
+// A type that holds a pointer that can be read or written atomically
+// (i.e., without word-tearing.)
+class AtomicPointer {
+ private:
+  intptr_t rep_;
+ public:
+  // Initialize to arbitrary value
+  AtomicPointer();
+
+  // Initialize to hold v
+  explicit AtomicPointer(void* v) : rep_(v) { }
+
+  // Read and return the stored pointer with the guarantee that no
+  // later memory access (read or write) by this thread can be
+  // reordered ahead of this read.
+  void* Acquire_Load() const;
+
+  // Set v as the stored pointer with the guarantee that no earlier
+  // memory access (read or write) by this thread can be reordered
+  // after this store.
+  void Release_Store(void* v);
+
+  // Read the stored pointer with no ordering guarantees.
+  void* NoBarrier_Load() const;
+
+  // Set va as the stored pointer with no ordering guarantees.
+  void NoBarrier_Store(void* v);
+};
+
+// ------------------ Checksumming -------------------
+
+// Store a 160-bit hash of "data[0..len-1]" in "hash_array[0]..hash_array[19]"
+extern void SHA1_Hash(const char* data, size_t len, char* hash_array);
+
+// ------------------ Compression -------------------
+
+// Store the lightweight compression of "input[0,input_length-1]" in *output.
+extern void Lightweight_Compress(const char* input, size_t input_length,
+                           std::string* output);
+
+// Attempt to lightweight uncompress input[0,input_length-1] into *output.
+// Returns true if successful, false if the input is invalid lightweight
+// compressed data.
+extern bool Lightweight_Uncompress(const char* input_data, size_t input_length,
+                             std::string* output);
+
+// ------------------ Miscellaneous -------------------
+
+// If heap profiling is not supported, returns false.
+// Else repeatedly calls (*func)(arg, data, n) and then returns true.
+// The concatenation of all "data[0,n-1]" fragments is the heap profile.
+extern bool GetHeapProfile(void (*func)(void*, const char*, int), void* arg);
+
+}
+}
+
+#endif  // STORAGE_LEVELDB_PORT_PORT_EXAMPLE_H_
diff --git a/port/port_posix.cc b/port/port_posix.cc
new file mode 100644
index 0000000..e75da8b
--- /dev/null
+++ b/port/port_posix.cc
@@ -0,0 +1,50 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#include "port/port_posix.h"
+
+#include <cstdlib>
+#include <stdio.h>
+#include <string.h>
+#include "util/logging.h"
+
+namespace leveldb {
+namespace port {
+
+static void PthreadCall(const char* label, int result) {
+  if (result != 0) {
+    fprintf(stderr, "pthread %s: %s\n", label, strerror(result));
+    abort();
+  }
+}
+
+Mutex::Mutex() { PthreadCall("init mutex", pthread_mutex_init(&mu_, NULL)); }
+
+Mutex::~Mutex() { PthreadCall("destroy mutex", pthread_mutex_destroy(&mu_)); }
+
+void Mutex::Lock() { PthreadCall("lock", pthread_mutex_lock(&mu_)); }
+
+void Mutex::Unlock() { PthreadCall("unlock", pthread_mutex_unlock(&mu_)); }
+
+CondVar::CondVar(Mutex* mu)
+    : mu_(mu) {
+    PthreadCall("init cv", pthread_cond_init(&cv_, NULL));
+}
+
+CondVar::~CondVar() { PthreadCall("destroy cv", pthread_cond_destroy(&cv_)); }
+
+void CondVar::Wait() {
+  PthreadCall("wait", pthread_cond_wait(&cv_, &mu_->mu_));
+}
+
+void CondVar::Signal() {
+  PthreadCall("signal", pthread_cond_signal(&cv_));
+}
+
+void CondVar::SignalAll() {
+  PthreadCall("broadcast", pthread_cond_broadcast(&cv_));
+}
+
+}
+}
diff --git a/port/port_posix.h b/port/port_posix.h
new file mode 100644
index 0000000..e7bc5b8
--- /dev/null
+++ b/port/port_posix.h
@@ -0,0 +1,108 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+//
+// See port_example.h for documentation for the following types/functions.
+
+#ifndef STORAGE_LEVELDB_PORT_PORT_POSIX_H_
+#define STORAGE_LEVELDB_PORT_PORT_POSIX_H_
+
+#include <endian.h>
+#include <pthread.h>
+#include <stdint.h>
+#include <string>
+#include <cstdatomic>
+#include <cstring>
+#include "port/sha1_portable.h"
+
+namespace leveldb {
+namespace port {
+
+static const bool kLittleEndian = (__BYTE_ORDER == __LITTLE_ENDIAN);
+
+class CondVar;
+
+class Mutex {
+ public:
+  Mutex();
+  ~Mutex();
+
+  void Lock();
+  void Unlock();
+  void AssertHeld() { }
+
+ private:
+  friend class CondVar;
+  pthread_mutex_t mu_;
+
+  // No copying
+  Mutex(const Mutex&);
+  void operator=(const Mutex&);
+};
+
+class CondVar {
+ public:
+  explicit CondVar(Mutex* mu);
+  ~CondVar();
+  void Wait();
+  void Signal();
+  void SignalAll();
+ private:
+  pthread_cond_t cv_;
+  Mutex* mu_;
+};
+
+// Storage for a lock-free pointer
+class AtomicPointer {
+ private:
+  std::atomic<void*> rep_;
+ public:
+  AtomicPointer() { }
+  explicit AtomicPointer(void* v) : rep_(v) { }
+  inline void* Acquire_Load() const {
+    return rep_.load(std::memory_order_acquire);
+  }
+  inline void Release_Store(void* v) {
+    rep_.store(v, std::memory_order_release);
+  }
+  inline void* NoBarrier_Load() const {
+    return rep_.load(std::memory_order_relaxed);
+  }
+  inline void NoBarrier_Store(void* v) {
+    rep_.store(v, std::memory_order_relaxed);
+  }
+};
+
+inline void SHA1_Hash(const char* data, size_t len, char* hash_array) {
+  SHA1_Hash_Portable(data, len, hash_array);
+}
+
+/**
+ * TODO(gabor): Implement actual compress
+ *     This is a hack - it just copies input to output.
+ *     No actual compression occurs.
+ */
+inline void Lightweight_Compress(const char* input, size_t input_length,
+                           std::string* output) {
+  output->assign(input, input_length);
+}
+
+/**
+ * TODO(gabor): Implement actual uncompress
+ *     This is a hack - it just copies input to output.
+ *     No actual uncompression occurs.
+ */
+inline bool Lightweight_Uncompress(const char* input_data, size_t input_length,
+                             std::string* output) {
+  output->assign(input_data, input_length);
+  return true;
+}
+
+inline bool GetHeapProfile(void (*func)(void*, const char*, int), void* arg) {
+  return false;
+}
+
+}
+}
+
+#endif  // STORAGE_LEVELDB_PORT_PORT_POSIX_H_
diff --git a/port/sha1_portable.cc b/port/sha1_portable.cc
new file mode 100644
index 0000000..8fa7277
--- /dev/null
+++ b/port/sha1_portable.cc
@@ -0,0 +1,298 @@
+// Portions copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+//
+// This module provides a slow but portable implementation of
+// the SHA1 hash function.
+//
+// It is adapted from free code written by Paul E. Jones
+// <paulej@packetizer.com>.  See http://www.packetizer.com/security/sha1/
+//
+// The license for the original code is:
+/*
+  Copyright (C) 1998, 2009
+  Paul E. Jones <paulej@packetizer.com>
+
+  Freeware Public License (FPL)
+
+  This software is licensed as "freeware."  Permission to distribute
+  this software in source and binary forms, including incorporation
+  into other products, is hereby granted without a fee.  THIS SOFTWARE
+  IS PROVIDED 'AS IS' AND WITHOUT ANY EXPRESSED OR IMPLIED WARRANTIES,
+  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+  AND FITNESS FOR A PARTICULAR PURPOSE.  THE AUTHOR SHALL NOT BE HELD
+  LIABLE FOR ANY DAMAGES RESULTING FROM THE USE OF THIS SOFTWARE, EITHER
+  DIRECTLY OR INDIRECTLY, INCLUDING, BUT NOT LIMITED TO, LOSS OF DATA
+  OR DATA BEING RENDERED INACCURATE.
+*/
+
+#include "port/sha1_portable.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+
+namespace leveldb {
+namespace port {
+
+/*
+ *  Description:
+ *      This class implements the Secure Hashing Standard as defined
+ *      in FIPS PUB 180-1 published April 17, 1995.
+ */
+
+/*
+ *  This structure will hold context information for the hashing
+ *  operation
+ */
+typedef struct SHA1Context {
+  unsigned Message_Digest[5]; /* Message Digest (output)          */
+
+  unsigned Length_Low;        /* Message length in bits           */
+  unsigned Length_High;       /* Message length in bits           */
+
+  unsigned char Message_Block[64]; /* 512-bit message blocks      */
+  int Message_Block_Index;    /* Index into message block array   */
+
+  bool Computed;               /* Is the digest computed?          */
+  bool Corrupted;              /* Is the message digest corruped?  */
+} SHA1Context;
+
+/*
+ *  Portability Issues:
+ *      SHA-1 is defined in terms of 32-bit "words".  This code was
+ *      written with the expectation that the processor has at least
+ *      a 32-bit machine word size.  If the machine word size is larger,
+ *      the code should still function properly.  One caveat to that
+ *      is that the input functions taking characters and character
+ *      arrays assume that only 8 bits of information are stored in each
+ *      character.
+ */
+
+/*
+ *  Define the circular shift macro
+ */
+#define SHA1CircularShift(bits,word) \
+                ((((word) << (bits)) & 0xFFFFFFFF) | \
+                ((word) >> (32-(bits))))
+
+/* Function prototypes */
+static void SHA1ProcessMessageBlock(SHA1Context *);
+static void SHA1PadMessage(SHA1Context *);
+
+// Initialize the SHA1Context in preparation for computing a new
+// message digest.
+static void SHA1Reset(SHA1Context* context) {
+  context->Length_Low             = 0;
+  context->Length_High            = 0;
+  context->Message_Block_Index    = 0;
+
+  context->Message_Digest[0]      = 0x67452301;
+  context->Message_Digest[1]      = 0xEFCDAB89;
+  context->Message_Digest[2]      = 0x98BADCFE;
+  context->Message_Digest[3]      = 0x10325476;
+  context->Message_Digest[4]      = 0xC3D2E1F0;
+
+  context->Computed   = false;
+  context->Corrupted  = false;
+}
+
+// This function will return the 160-bit message digest into the
+// Message_Digest array within the SHA1Context provided
+static bool SHA1Result(SHA1Context *context) {
+  if (context->Corrupted) {
+    return false;
+  }
+
+  if (!context->Computed) {
+    SHA1PadMessage(context);
+    context->Computed = true;
+  }
+  return true;
+}
+
+// This function accepts an array of bytes as the next portion of
+// the message.
+static void SHA1Input(SHA1Context         *context,
+                      const unsigned char *message_array,
+                      unsigned            length) {
+  if (!length) return;
+
+  if (context->Computed || context->Corrupted) {
+    context->Corrupted = true;
+    return;
+  }
+
+  while(length-- && !context->Corrupted) {
+    context->Message_Block[context->Message_Block_Index++] =
+        (*message_array & 0xFF);
+
+    context->Length_Low += 8;
+    /* Force it to 32 bits */
+    context->Length_Low &= 0xFFFFFFFF;
+    if (context->Length_Low == 0) {
+      context->Length_High++;
+      /* Force it to 32 bits */
+      context->Length_High &= 0xFFFFFFFF;
+      if (context->Length_High == 0)
+      {
+        /* Message is too long */
+        context->Corrupted = true;
+      }
+    }
+
+    if (context->Message_Block_Index == 64)
+    {
+      SHA1ProcessMessageBlock(context);
+    }
+
+    message_array++;
+  }
+}
+
+// This function will process the next 512 bits of the message stored
+// in the Message_Block array.
+static void SHA1ProcessMessageBlock(SHA1Context *context) {
+  const unsigned K[] =            // Constants defined in SHA-1
+      {
+        0x5A827999,
+        0x6ED9EBA1,
+        0x8F1BBCDC,
+        0xCA62C1D6
+      };
+  int         t;                  // Loop counter
+  unsigned    temp;               // Temporary word value
+  unsigned    W[80];            // Word sequence
+  unsigned    A, B, C, D, E;    // Word buffers
+
+  // Initialize the first 16 words in the array W
+  for(t = 0; t < 16; t++) {
+    W[t] = ((unsigned) context->Message_Block[t * 4]) << 24;
+    W[t] |= ((unsigned) context->Message_Block[t * 4 + 1]) << 16;
+    W[t] |= ((unsigned) context->Message_Block[t * 4 + 2]) << 8;
+    W[t] |= ((unsigned) context->Message_Block[t * 4 + 3]);
+  }
+
+  for(t = 16; t < 80; t++) {
+    W[t] = SHA1CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
+  }
+
+  A = context->Message_Digest[0];
+  B = context->Message_Digest[1];
+  C = context->Message_Digest[2];
+  D = context->Message_Digest[3];
+  E = context->Message_Digest[4];
+
+  for(t = 0; t < 20; t++) {
+    temp =  SHA1CircularShift(5,A) +
+        ((B & C) | ((~B) & D)) + E + W[t] + K[0];
+    temp &= 0xFFFFFFFF;
+    E = D;
+    D = C;
+    C = SHA1CircularShift(30,B);
+    B = A;
+    A = temp;
+  }
+
+  for(t = 20; t < 40; t++) {
+    temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
+    temp &= 0xFFFFFFFF;
+    E = D;
+    D = C;
+    C = SHA1CircularShift(30,B);
+    B = A;
+    A = temp;
+  }
+
+  for(t = 40; t < 60; t++) {
+    temp = SHA1CircularShift(5,A) +
+        ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
+    temp &= 0xFFFFFFFF;
+    E = D;
+    D = C;
+    C = SHA1CircularShift(30,B);
+    B = A;
+    A = temp;
+  }
+
+  for(t = 60; t < 80; t++) {
+    temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
+    temp &= 0xFFFFFFFF;
+    E = D;
+    D = C;
+    C = SHA1CircularShift(30,B);
+    B = A;
+    A = temp;
+  }
+
+  context->Message_Digest[0] = (context->Message_Digest[0] + A) & 0xFFFFFFFF;
+  context->Message_Digest[1] = (context->Message_Digest[1] + B) & 0xFFFFFFFF;
+  context->Message_Digest[2] = (context->Message_Digest[2] + C) & 0xFFFFFFFF;
+  context->Message_Digest[3] = (context->Message_Digest[3] + D) & 0xFFFFFFFF;
+  context->Message_Digest[4] = (context->Message_Digest[4] + E) & 0xFFFFFFFF;
+
+  context->Message_Block_Index = 0;
+}
+
+// According to the standard, the message must be padded to an even
+// 512 bits.  The first padding bit must be a '1'.  The last 64 bits
+// represent the length of the original message.  All bits in between
+// should be 0.  This function will pad the message according to those
+// rules by filling the Message_Block array accordingly.  It will also
+// call SHA1ProcessMessageBlock() appropriately.  When it returns, it
+// can be assumed that the message digest has been computed.
+static void SHA1PadMessage(SHA1Context *context) {
+  // Check to see if the current message block is too small to hold
+  // the initial padding bits and length.  If so, we will pad the
+  // block, process it, and then continue padding into a second block.
+  if (context->Message_Block_Index > 55) {
+    context->Message_Block[context->Message_Block_Index++] = 0x80;
+    while(context->Message_Block_Index < 64) {
+      context->Message_Block[context->Message_Block_Index++] = 0;
+    }
+
+    SHA1ProcessMessageBlock(context);
+
+    while(context->Message_Block_Index < 56) {
+      context->Message_Block[context->Message_Block_Index++] = 0;
+    }
+  } else {
+    context->Message_Block[context->Message_Block_Index++] = 0x80;
+    while(context->Message_Block_Index < 56) {
+      context->Message_Block[context->Message_Block_Index++] = 0;
+    }
+  }
+
+  // Store the message length as the last 8 octets
+  context->Message_Block[56] = (context->Length_High >> 24) & 0xFF;
+  context->Message_Block[57] = (context->Length_High >> 16) & 0xFF;
+  context->Message_Block[58] = (context->Length_High >> 8) & 0xFF;
+  context->Message_Block[59] = (context->Length_High) & 0xFF;
+  context->Message_Block[60] = (context->Length_Low >> 24) & 0xFF;
+  context->Message_Block[61] = (context->Length_Low >> 16) & 0xFF;
+  context->Message_Block[62] = (context->Length_Low >> 8) & 0xFF;
+  context->Message_Block[63] = (context->Length_Low) & 0xFF;
+
+  SHA1ProcessMessageBlock(context);
+}
+
+
+void SHA1_Hash_Portable(const char* data, size_t len, char* hash_array) {
+  SHA1Context context;
+  SHA1Reset(&context);
+  SHA1Input(&context, reinterpret_cast<const unsigned char*>(data), len);
+  bool ok = SHA1Result(&context);
+  if (!ok) {
+    fprintf(stderr, "Unexpected error in SHA1_Hash_Portable code\n");
+    exit(1);
+  }
+  for (int i = 0; i < 5; i++) {
+    uint32_t value = context.Message_Digest[i];
+    hash_array[i*4 + 0] = (value >> 24) & 0xff;
+    hash_array[i*4 + 1] = (value >> 16) & 0xff;
+    hash_array[i*4 + 2] = (value >> 8) & 0xff;
+    hash_array[i*4 + 3] = value & 0xff;
+  }
+}
+
+}
+}
diff --git a/port/sha1_portable.h b/port/sha1_portable.h
new file mode 100644
index 0000000..31db305
--- /dev/null
+++ b/port/sha1_portable.h
@@ -0,0 +1,25 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#ifndef STORAGE_LEVELDB_PORT_SHA1_PORTABLE_H_
+#define STORAGE_LEVELDB_PORT_SHA1_PORTABLE_H_
+
+#include <stddef.h>
+
+namespace leveldb {
+namespace port {
+
+// Compute the SHA1 hash value of "data[0..len-1]" and store it in
+// "hash_array[0..19]".  hash_array must have 20 bytes of space available.
+//
+// This function is portable but may not be as fast as a version
+// optimized for your platform.  It is provided as a default method
+// that can be used when porting leveldb to a new platform if no
+// better SHA1 hash implementation is available.
+void SHA1_Hash_Portable(const char* data, size_t len, char* hash_array);
+
+}
+}
+
+#endif  // STORAGE_LEVELDB_PORT_SHA1_PORTABLE_H_
diff --git a/port/sha1_test.cc b/port/sha1_test.cc
new file mode 100644
index 0000000..46bbeba
--- /dev/null
+++ b/port/sha1_test.cc
@@ -0,0 +1,55 @@
+// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file. See the AUTHORS file for names of contributors.
+
+#include "port/port.h"
+#include "util/testharness.h"
+
+namespace leveldb {
+namespace port {
+
+class SHA1 { };
+
+static std::string TestSHA1(const char* data, size_t len) {
+  char hash_val[20];
+  SHA1_Hash(data, len, hash_val);
+  char buf[41];
+  for (int i = 0; i < 20; i++) {
+    snprintf(buf + i * 2, 41 - i * 2,
+             "%02x",
+             static_cast<unsigned int>(static_cast<unsigned char>(
+                 hash_val[i])));
+  }
+  return std::string(buf, 40);
+}
+
+TEST(SHA1, Simple) {
+  ASSERT_EQ("da39a3ee5e6b4b0d3255bfef95601890afd80709", TestSHA1("", 0));
+  ASSERT_EQ("aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d", TestSHA1("hello", 5));
+  std::string x(10000, 'x');
+  ASSERT_EQ("f8c5cde791c5056cf515881e701c8a9ecb439a75",
+            TestSHA1(x.data(), x.size()));
+}
+
+TEST(SHA1, Benchmark) {
+  std::string data(1048576 * 100, 'x');
+  double start = Env::Default()->NowMicros() * 1e-6;
+  static const int kIters = 10;
+  uint32_t sha1 = 0;
+  for (int i = 0; i < kIters; i++) {
+    char hash_val[20];
+    SHA1_Hash(data.data(), data.size(), hash_val);
+    sha1 |= hash_val[0];
+  }
+  double finish = Env::Default()->NowMicros() * 1e-6;
+  double mb = (static_cast<long long int>(data.size()) * kIters) / 1048576.0;
+  fprintf(stderr, "SHA1 %0.0f MB: %.3f secs; %.1f MB/s, dummy=0x%02x\n",
+          mb, (finish - start), mb / (finish - start), sha1);
+}
+
+}
+}
+
+int main(int argc, char** argv) {
+  return leveldb::test::RunAllTests();
+}