[Courgette] Refactor BSDiff namespaces and bsdiff::search() interface.

courgette/third_party/bsdiff/qsufsort.h

-/*
-  qsufsort.h -- Suffix array generation.
+// Copyright 2003, 2004 Colin Percival
+// All rights reserved
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted providing that the following conditions
+// are met:
+// 1. Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+// 2. 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.
+//
+// For the terms under which this work may be distributed, please see
+// the adjoining file "LICENSE".
+//
+// qsufsort.h -- Suffix array generation.
+//
+// ChangeLog:
+// 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
+//              values throughout.
+//                --Benjamin Smedberg <benjamin@smedbergs.us>
+// 2010-05-26 - Use a paged array for V and I. The address space may be too
+//              fragmented for these big arrays to be contiguous.
+//                --Stephen Adams <sra@chromium.org>
+// 2015-08-03 - Extract QSufSort to a separate file as template.
+//                --Samuel Huang <huangs@chromium.org>
+// 2015-08-19 - Optimize split(), add comments.
+//                --Samuel Huang <huangs@chromium.org>
+// 2016-04-27 - Change split() to use Bentley & McIlroy's pivot selection
+//              algorithm, which QSufSort originally used. Reference:
+//              http://www.larsson.dogma.net/qsufsort.c
+//                --Samuel Huang <huangs@chromium.org>
 
-  Copyright 2003 Colin Percival
-
-  For the terms under which this work may be distributed, please see
-  the adjoining file "LICENSE".
-
-  ChangeLog:
-  2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
-               values throughout.
-                 --Benjamin Smedberg <benjamin@smedbergs.us>
-  2010-05-26 - Use a paged array for V and I. The address space may be too
-               fragmented for these big arrays to be contiguous.
-                 --Stephen Adams <sra@chromium.org>
-  2015-08-03 - Extract QSufSort to a separate file as template.
-                 --Samuel Huang <huangs@chromium.org>
-  2015-08-19 - Optimize split() and search(), add comments.
-                 --Samuel Huang <huangs@chromium.org>
-  2016-04-27 - Change split() to use Bentley & McIlroy's pivot selection
-               algorithm, which QSufSort originally used. Reference:
-               http://www.larsson.dogma.net/qsufsort.c
-                 --Samuel Huang <huangs@chromium.org>
-*/
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
 
 #ifndef COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_
 #define COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_
 
-#include <algorithm>
-#include <cstring>
-
-namespace courgette {
 namespace qsuf {
 
 // ------------------------------------------------------------------------
 //
 // The following code is taken verbatim from 'bsdiff.c'. Please keep all the
 // code formatting and variable names.  The changes from the original are:
 // (1) replacing tabs with spaces,
 // (2) indentation and spacing,
 // (3) using 'const',
 // (4) changing the V and I parameters from int* to template <typename T>.
-// (5) optimizing split() and search(); fix styles.
+// (5) optimizing split(); fix styles.
+// (6) moving matchlen() and search() to a separate file.
 //
 // The code appears to be a rewritten version of the suffix array algorithm
 // presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko
 // Sadakane, special cased for bytes.
 
 namespace {
 
 template <typename T>
 T median3(const T& a, const T& b, const T& c) {
   if (a < b)
@@ skipping 137 matching lines @@
       };
     };
     if (len)
       I[i - len] = -len;
   };
 
   for (i = 0; i < oldsize + 1; i++)
     I[V[i]] = i;
 }
 
-static int matchlen(const unsigned char* old,
-                    int oldsize,
-                    const unsigned char* newbuf,
-                    int newsize) {
-  int i;
-
-  for (i = 0; (i < oldsize) && (i < newsize); i++)
-    if (old[i] != newbuf[i])
-      break;
-
-  return i;
-}
-
-template <class T>
-static int search(T I,
-                  const unsigned char* old,
-                  int oldsize,
-                  const unsigned char* newbuf,
-                  int newsize,
-                  int* pos) {
-  int lo = 0;
-  int hi = oldsize;
-  while (hi - lo >= 2) {
-    int mid = (lo + hi) / 2;
-    if (memcmp(old + I[mid], newbuf, std::min(oldsize - I[mid], newsize)) < 0) {
-      lo = mid;
-    } else {
-      hi = mid;
-    }
-  }
-
-  int x = matchlen(old + I[lo], oldsize - I[lo], newbuf, newsize);
-  int y = matchlen(old + I[hi], oldsize - I[hi], newbuf, newsize);
-  if (x > y) {
-    *pos = I[lo];
-    return x;
-  }
-  *pos = I[hi];
-  return y;
-}
-
 //  End of 'verbatim' code.
 // ------------------------------------------------------------------------
 
 }  // namespace qsuf
-}  // namespace courgette
+
 #endif  // COURGETTE_THIRD_PARTY_BSDIFF_QSUFSORT_H_