text: /* jshint node: true */
  
  // TODO: Make long comparison impervious to precision loss.
  // TODO: Optimize binary comparison methods.
  
  'use strict';
  
  /** Various utilities used across this library. */
  
  var crypto = require('crypto');
  var util = require('util');
  
  // Shared buffer pool for all taps.
  var POOL = new BufferPool(4096);
  
  
  /**
   * Uppercase the first letter of a string.
   *
   * @param s {String} The string.
   */
  function capitalize(s) { return s.charAt(0).toUpperCase() + s.slice(1); }
  
  /**
   * Compare two numbers.
   *
   * @param n1 {Number} The first one.
   * @param n2 {Number} The second one.
   */
  function compare(n1, n2) { return n1 === n2 ? 0 : (n1 < n2 ? -1 : 1); }
  
  /**
   * Get option or default if undefined.
   *
   * @param opts {Object} Options.
   * @param key {String} Name of the option.
   * @param def {...} Default value.
   *
   * This is useful mostly for true-ish defaults and false-ish values (where the
   * usual `||` idiom breaks down).
   */
  function getOption(opts, key, def) {
    var value = opts[key];
    return value === undefined ? def : value;
  }
  
  /**
   * Compute a string's hash.
   *
   * @param str {String} The string to hash.
   * @param algorithm {String} The algorithm used. Defaults to MD5.
   */
  function getHash(str, algorithm) {
    algorithm = algorithm || 'md5';
    var hash = crypto.createHash(algorithm);
    hash.end(str);
    return hash.read();
  }
  
  /**
   * Find index of value in array.
   *
   * @param arr {Array} Can also be a false-ish value.
   * @param v {Object} Value to find.
   *
   * Returns -1 if not found, -2 if found multiple times.
   */
  function singleIndexOf(arr, v) {
    var pos = -1;
    var i, l;
    if (!arr) {
      return -1;
    }
    for (i = 0, l = arr.length; i < l; i++) {
      if (arr[i] === v) {
        if (pos >= 0) {
          return -2;
        }
        pos = i;
      }
    }
    return pos;
  }
  
  /**
   * Convert array to map.
   *
   * @param arr {Array} Elements.
   * @param fn {Function} Function returning an element's key.
   */
  function toMap(arr, fn) {
    var obj = {};
    var i, elem;
    for (i = 0; i < arr.length; i++) {
      elem = arr[i];
      obj[fn(elem)] = elem;
    }
    return obj;
  }
  
  /**
   * Convert map to array of values (polyfill for `Object.values`).
   *
   * @param obj {Object} Map.
   */
  function objectValues(obj) {
    return Object.keys(obj).map(function (key) { return obj[key]; });
  }
  
  /**
   * Check whether an array has duplicates.
   *
   * @param arr {Array} The array.
   * @param fn {Function} Optional function to apply to each element.
   */
  function hasDuplicates(arr, fn) {
    var obj = {};
    var i, l, elem;
    for (i = 0, l = arr.length; i < l; i++) {
      elem = arr[i];
      if (fn) {
        elem = fn(elem);
      }
      if (obj[elem]) {
        return true;
      }
      obj[elem] = true;
    }
    return false;
  }
  
  /**
   * Copy properties from one object to another.
   *
   * @param src {Object} The source object.
   * @param dst {Object} The destination object.
   * @param overwrite {Boolean} Whether to overwrite existing destination
   * properties. Defaults to false.
   */
  function copyOwnProperties(src, dst, overwrite) {
    var names = Object.getOwnPropertyNames(src);
    var i, l, name;
    for (i = 0, l = names.length; i < l; i++) {
      name = names[i];
      if (!dst.hasOwnProperty(name) || overwrite) {
        var descriptor = Object.getOwnPropertyDescriptor(src, name);
        Object.defineProperty(dst, name, descriptor);
      }
    }
    return dst;
  }
  
  /**
   * Returns offset in the string of the end of JSON object (-1 if past the end).
   *
   * To keep the implementation simple, this function isn't a JSON validator. It
   * will gladly return a result for invalid JSON (which is OK since that will be
   * promptly rejected by the JSON parser). What matters is that it is guaranteed
   * to return the correct end when presented with valid JSON.
   *
   * @param str {String} Input string containing serialized JSON..
   * @param pos {Number} Starting position.
   */
  function jsonEnd(str, pos) {
    pos = pos | 0;
  
    // Handle the case of a simple literal separately.
    var c = str.charAt(pos++);
    if (/[\d-]/.test(c)) {
      while (/[eE\d.+-]/.test(str.charAt(pos))) {
        pos++;
      }
      return pos;
    } else if (/true|null/.test(str.slice(pos - 1, pos + 3))) {
      return pos + 3;
    } else if (/false/.test(str.slice(pos - 1, pos + 4))) {
      return pos + 4;
    }
  
    // String, object, or array.
    var depth = 0;
    var literal = false;
    do {
      switch (c) {
      case '{':
      case '[':
        if (!literal) { depth++; }
        break;
      case '}':
      case ']':
        if (!literal && !--depth) {
          return pos;
        }
        break;
      case '"':
        literal = !literal;
        if (!depth && !literal) {
          return pos;
        }
        break;
      case '\\':
        pos++; // Skip the next character.
      }
    } while ((c = str.charAt(pos++)));
  
    return -1;
  }
  
  /** "Abstract" function to help with "subclassing". */
  function abstractFunction() { throw new Error('abstract'); }
  
  /** Batch-deprecate "getters" from an object's prototype. */
  function addDeprecatedGetters(obj, props) {
    var proto = obj.prototype;
    var i, l, prop, getter;
    for (i = 0, l = props.length; i < l; i++) {
      prop = props[i];
      getter = 'get' + capitalize(prop);
      proto[getter] = util.deprecate(
        createGetter(prop),
        'use `.' + prop + '` instead of `.' + getter + '()`'
      );
    }
  
    function createGetter(prop) {
      return function () {
        var delegate = this[prop];
        return typeof delegate == 'function' ?
          delegate.apply(this, arguments) :
          delegate;
      };
    }
  }
  
  /**
   * Simple buffer pool to avoid allocating many small buffers.
   *
   * This provides significant speedups in recent versions of node (6+).
   */
  function BufferPool(len) {
    this._len = len | 0;
    this._pos = 0;
    this._slab = new Buffer(this._len);
  }
  
  BufferPool.prototype.alloc = function (len) {
    var maxLen = this._len;
    if (len > maxLen) {
      return new Buffer(len);
    }
    if (this._pos + len > maxLen) {
      this._slab = new Buffer(maxLen);
      this._pos = 0;
    }
    return this._slab.slice(this._pos, this._pos += len);
  };
  
  /**
   * Generator of random things.
   *
   * Inspired by: http://stackoverflow.com/a/424445/1062617
   */
  function Lcg(seed) {
    var a = 1103515245;
    var c = 12345;
    var m = Math.pow(2, 31);
    var state = Math.floor(seed || Math.random() * (m - 1));
  
    this._max = m;
    this._nextInt = function () { return state = (a * state + c) % m; };
  }
  
  Lcg.prototype.nextBoolean = function () {
    // jshint -W018
    return !!(this._nextInt() % 2);
  };
  
  Lcg.prototype.nextInt = function (start, end) {
    if (end === undefined) {
      end = start;
      start = 0;
    }
    end = end === undefined ? this._max : end;
    return start + Math.floor(this.nextFloat() * (end - start));
  };
  
  Lcg.prototype.nextFloat = function (start, end) {
    if (end === undefined) {
      end = start;
      start = 0;
    }
    end = end === undefined ? 1 : end;
    return start + (end - start) * this._nextInt() / this._max;
  };
  
  Lcg.prototype.nextString = function(len, flags) {
    len |= 0;
    flags = flags || 'aA';
    var mask = '';
    if (flags.indexOf('a') > -1) {
      mask += 'abcdefghijklmnopqrstuvwxyz';
    }
    if (flags.indexOf('A') > -1) {
      mask += 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    }
    if (flags.indexOf('#') > -1) {
      mask += '0123456789';
    }
    if (flags.indexOf('!') > -1) {
      mask += '~`!@#$%^&*()_+-={}[]:";\'<>?,./|\\';
    }
    var result = [];
    for (var i = 0; i < len; i++) {
      result.push(this.choice(mask));
    }
    return result.join('');
  };
  
  Lcg.prototype.nextBuffer = function (len) {
    var arr = [];
    var i;
    for (i = 0; i < len; i++) {
      arr.push(this.nextInt(256));
    }
    return new Buffer(arr);
  };
  
  Lcg.prototype.choice = function (arr) {
    var len = arr.length;
    if (!len) {
      throw new Error('choosing from empty array');
    }
    return arr[this.nextInt(len)];
  };
  
  /**
   * Ordered queue which returns items consecutively.
   *
   * This is actually a heap by index, with the added requirements that elements
   * can only be retrieved consecutively.
   */
  function OrderedQueue() {
    this._index = 0;
    this._items = [];
  }
  
  OrderedQueue.prototype.push = function (item) {
    var items = this._items;
    var i = items.length | 0;
    var j;
    items.push(item);
    while (i > 0 && items[i].index < items[j = ((i - 1) >> 1)].index) {
      item = items[i];
      items[i] = items[j];
      items[j] = item;
      i = j;
    }
  };
  
  OrderedQueue.prototype.pop = function () {
    var items = this._items;
    var len = (items.length - 1) | 0;
    var first = items[0];
    if (!first || first.index > this._index) {
      return null;
    }
    this._index++;
    if (!len) {
      items.pop();
      return first;
    }
    items[0] = items.pop();
    var mid = len >> 1;
    var i = 0;
    var i1, i2, j, item, c, c1, c2;
    while (i < mid) {
      item = items[i];
      i1 = (i << 1) + 1;
      i2 = (i + 1) << 1;
      c1 = items[i1];
      c2 = items[i2];
      if (!c2 || c1.index <= c2.index) {
        c = c1;
        j = i1;
      } else {
        c = c2;
        j = i2;
      }
      if (c.index >= item.index) {
        break;
      }
      items[j] = item;
      items[i] = c;
      i = j;
    }
    return first;
  };
  
  /**
   * A tap is a buffer which remembers what has been already read.
   *
   * It is optimized for performance, at the cost of failing silently when
   * overflowing the buffer. This is a purposeful trade-off given the expected
   * rarity of this case and the large performance hit necessary to enforce
   * validity. See `isValid` below for more information.
   */
  function Tap(buf, pos) {
    this.buf = buf;
    this.pos = pos | 0;
    if (this.pos < 0) {
      throw new Error('negative offset');
    }
  }
  
  /**
   * Check that the tap is in a valid state.
   *
   * For efficiency reasons, none of the methods below will fail if an overflow
   * occurs (either read, skip, or write). For this reason, it is up to the
   * caller to always check that the read, skip, or write was valid by calling
   * this method.
   */
  Tap.prototype.isValid = function () { return this.pos <= this.buf.length; };
  
  // Read, skip, write methods.
  //
  // These should fail silently when the buffer overflows. Note this is only
  // required to be true when the functions are decoding valid objects. For
  // example errors will still be thrown if a bad count is read, leading to a
  // negative position offset (which will typically cause a failure in
  // `readFixed`).
  
  Tap.prototype.readBoolean = function () { return !!this.buf[this.pos++]; };
  
  Tap.prototype.skipBoolean = function () { this.pos++; };
  
  Tap.prototype.writeBoolean = function (b) { this.buf[this.pos++] = !!b; };
  
  Tap.prototype.readInt = Tap.prototype.readLong = function () {
    var n = 0;
    var k = 0;
    var buf = this.buf;
    var b, h, f, fk;
  
    do {
      b = buf[this.pos++];
      h = b & 0x80;
      n |= (b & 0x7f) << k;
      k += 7;
    } while (h && k < 28);
  
    if (h) {
      // Switch to float arithmetic, otherwise we might overflow.
      f = n;
      fk = 268435456; // 2 ** 28.
      do {
        b = buf[this.pos++];
        f += (b & 0x7f) * fk;
        fk *= 128;
      } while (b & 0x80);
      return (f % 2 ? -(f + 1) : f) / 2;
    }
  
    return (n >> 1) ^ -(n & 1);
  };
  
  Tap.prototype.skipInt = Tap.prototype.skipLong = function () {
    var buf = this.buf;
    while (buf[this.pos++] & 0x80) {}
  };
  
  Tap.prototype.writeInt = Tap.prototype.writeLong = function (n) {
    var buf = this.buf;
    var f, m;
  
    if (n >= -1073741824 && n < 1073741824) {
      // Won't overflow, we can use integer arithmetic.
      m = n >= 0 ? n << 1 : (~n << 1) | 1;
      do {
        buf[this.pos] = m & 0x7f;
        m >>= 7;
      } while (m && (buf[this.pos++] |= 0x80));
    } else {
      // We have to use slower floating arithmetic.
      f = n >= 0 ? n * 2 : (-n * 2) - 1;
      do {
        buf[this.pos] = f & 0x7f;
        f /= 128;
      } while (f >= 1 && (buf[this.pos++] |= 0x80));
    }
    this.pos++;
  };
  
  Tap.prototype.readFloat = function () {
    var buf = this.buf;
    var pos = this.pos;
    this.pos += 4;
    if (this.pos > buf.length) {
      return;
    }
    return this.buf.readFloatLE(pos);
  };
  
  Tap.prototype.skipFloat = function () { this.pos += 4; };
  
  Tap.prototype.writeFloat = function (f) {
    var buf = this.buf;
    var pos = this.pos;
    this.pos += 4;
    if (this.pos > buf.length) {
      return;
    }
    return this.buf.writeFloatLE(f, pos);
  };
  
  Tap.prototype.readDouble = function () {
    var buf = this.buf;
    var pos = this.pos;
    this.pos += 8;
    if (this.pos > buf.length) {
      return;
    }
    return this.buf.readDoubleLE(pos);
  };
  
  Tap.prototype.skipDouble = function () { this.pos += 8; };
  
  Tap.prototype.writeDouble = function (d) {
    var buf = this.buf;
    var pos = this.pos;
    this.pos += 8;
    if (this.pos > buf.length) {
      return;
    }
    return this.buf.writeDoubleLE(d, pos);
  };
  
  Tap.prototype.readFixed = function (len) {
    var pos = this.pos;
    this.pos += len;
    if (this.pos > this.buf.length) {
      return;
    }
    var fixed = POOL.alloc(len);
    this.buf.copy(fixed, 0, pos, pos + len);
    return fixed;
  };
  
  Tap.prototype.skipFixed = function (len) { this.pos += len; };
  
  Tap.prototype.writeFixed = function (buf, len) {
    len = len || buf.length;
    var pos = this.pos;
    this.pos += len;
    if (this.pos > this.buf.length) {
      return;
    }
    buf.copy(this.buf, pos, 0, len);
  };
  
  Tap.prototype.readBytes = function () {
    return this.readFixed(this.readLong());
  };
  
  Tap.prototype.skipBytes = function () {
    var len = this.readLong();
    this.pos += len;
  };
  
  Tap.prototype.writeBytes = function (buf) {
    var len = buf.length;
    this.writeLong(len);
    this.writeFixed(buf, len);
  };
  
  /* istanbul ignore else */
  if (typeof Buffer.prototype.utf8Slice == 'function') {
    // Use this optimized function when available.
    Tap.prototype.readString = function () {
      var len = this.readLong();
      var pos = this.pos;
      var buf = this.buf;
      this.pos += len;
      if (this.pos > buf.length) {
        return;
      }
      return this.buf.utf8Slice(pos, pos + len);
    };
  } else {
    Tap.prototype.readString = function () {
      var len = this.readLong();
      var pos = this.pos;
      var buf = this.buf;
      this.pos += len;
      if (this.pos > buf.length) {
        return;
      }
      return this.buf.slice(pos, pos + len).toString();
    };
  }
  
  Tap.prototype.skipString = function () {
    var len = this.readLong();
    this.pos += len;
  };
  
  Tap.prototype.writeString = function (s) {
    var len = Buffer.byteLength(s);
    var buf = this.buf;
    this.writeLong(len);
    var pos = this.pos;
    this.pos += len;
    if (this.pos > buf.length) {
      return;
    }
    if (len > 64) {
      this._writeUtf8(s, len);
    } else {
      var i, l, c1, c2;
      for (i = 0, l = len; i < l; i++) {
        c1 = s.charCodeAt(i);
        if (c1 < 0x80) {
          buf[pos++] = c1;
        } else if (c1 < 0x800) {
          buf[pos++] = c1 >> 6 | 0xc0;
          buf[pos++] = c1 & 0x3f | 0x80;
        } else if (
          (c1 & 0xfc00) === 0xd800 &&
          ((c2 = s.charCodeAt(i + 1)) & 0xfc00) === 0xdc00
        ) {
          c1 = 0x10000 + ((c1 & 0x03ff) << 10) + (c2 & 0x03ff);
          i++;
          buf[pos++] = c1 >> 18 | 0xf0;
          buf[pos++] = c1 >> 12 & 0x3f | 0x80;
          buf[pos++] = c1 >> 6 & 0x3f | 0x80;
          buf[pos++] = c1 & 0x3f | 0x80;
        } else {
          buf[pos++] = c1 >> 12 | 0xe0;
          buf[pos++] = c1 >> 6 & 0x3f | 0x80;
          buf[pos++] = c1 & 0x3f | 0x80;
        }
      }
    }
  };
  
  /* istanbul ignore else */
  if (typeof Buffer.prototype.utf8Write == 'function') {
    Tap.prototype._writeUtf8 = function (str, len) {
      this.buf.utf8Write(str, this.pos - len, len);
    };
  } else {
    // `utf8Write` isn't available in the browser.
    Tap.prototype._writeUtf8 = function (str, len) {
      this.buf.write(str, this.pos - len, len, 'utf8');
    };
  }
  
  /* istanbul ignore else */
  if (typeof Buffer.prototype.latin1Write == 'function') {
    // `binaryWrite` has been renamed to `latin1Write` in Node v6.4.0, see
    // https://github.com/nodejs/node/pull/7111. Note that the `'binary'`
    // encoding argument still works however.
    Tap.prototype.writeBinary = function (str, len) {
      var pos = this.pos;
      this.pos += len;
      if (this.pos > this.buf.length) {
        return;
      }
      this.buf.latin1Write(str, pos, len);
    };
  } else if (typeof Buffer.prototype.binaryWrite == 'function') {
    Tap.prototype.writeBinary = function (str, len) {
      var pos = this.pos;
      this.pos += len;
      if (this.pos > this.buf.length) {
        return;
      }
      this.buf.binaryWrite(str, pos, len);
    };
  } else {
    // Slowest implementation.
    Tap.prototype.writeBinary = function (s, len) {
      var pos = this.pos;
      this.pos += len;
      if (this.pos > this.buf.length) {
        return;
      }
      this.buf.write(s, pos, len, 'binary');
    };
  }
  
  // Binary comparison methods.
  //
  // These are not guaranteed to consume the objects they are comparing when
  // returning a non-zero result (allowing for performance benefits), so no other
  // operations should be done on either tap after a compare returns a non-zero
  // value. Also, these methods do not have the same silent failure requirement
  // as read, skip, and write since they are assumed to be called on valid
  // buffers.
  
  Tap.prototype.matchBoolean = function (tap) {
    return this.buf[this.pos++] - tap.buf[tap.pos++];
  };
  
  Tap.prototype.matchInt = Tap.prototype.matchLong = function (tap) {
    var n1 = this.readLong();
    var n2 = tap.readLong();
    return n1 === n2 ? 0 : (n1 < n2 ? -1 : 1);
  };
  
  Tap.prototype.matchFloat = function (tap) {
    var n1 = this.readFloat();
    var n2 = tap.readFloat();
    return n1 === n2 ? 0 : (n1 < n2 ? -1 : 1);
  };
  
  Tap.prototype.matchDouble = function (tap) {
    var n1 = this.readDouble();
    var n2 = tap.readDouble();
    return n1 === n2 ? 0 : (n1 < n2 ? -1 : 1);
  };
  
  Tap.prototype.matchFixed = function (tap, len) {
    return this.readFixed(len).compare(tap.readFixed(len));
  };
  
  Tap.prototype.matchBytes = Tap.prototype.matchString = function (tap) {
    var l1 = this.readLong();
    var p1 = this.pos;
    this.pos += l1;
    var l2 = tap.readLong();
    var p2 = tap.pos;
    tap.pos += l2;
    var b1 = this.buf.slice(p1, this.pos);
    var b2 = tap.buf.slice(p2, tap.pos);
    return b1.compare(b2);
  };
  
  // Functions for supporting custom long classes.
  //
  // The two following methods allow the long implementations to not have to
  // worry about Avro's zigzag encoding, we directly expose longs as unpacked.
  
  Tap.prototype.unpackLongBytes = function () {
    var res = new Buffer(8);
    var n = 0;
    var i = 0; // Byte index in target buffer.
    var j = 6; // Bit offset in current target buffer byte.
    var buf = this.buf;
    var b, neg;
  
    b = buf[this.pos++];
    neg = b & 1;
    res.fill(0);
  
    n |= (b & 0x7f) >> 1;
    while (b & 0x80) {
      b = buf[this.pos++];
      n |= (b & 0x7f) << j;
      j += 7;
      if (j >= 8) {
        // Flush byte.
        j -= 8;
        res[i++] = n;
        n >>= 8;
      }
    }
    res[i] = n;
  
    if (neg) {
      invert(res, 8);
    }
  
    return res;
  };
  
  Tap.prototype.packLongBytes = function (buf) {
    var neg = (buf[7] & 0x80) >> 7;
    var res = this.buf;
    var j = 1;
    var k = 0;
    var m = 3;
    var n;
  
    if (neg) {
      invert(buf, 8);
      n = 1;
    } else {
      n = 0;
    }
  
    var parts = [
      buf.readUIntLE(0, 3),
      buf.readUIntLE(3, 3),
      buf.readUIntLE(6, 2)
    ];
    // Not reading more than 24 bits because we need to be able to combine the
    // "carry" bits from the previous part and JavaScript only supports bitwise
    // operations on 32 bit integers.
    while (m && !parts[--m]) {} // Skip trailing 0s.
  
    // Leading parts (if any), we never bail early here since we need the
    // continuation bit to be set.
    while (k < m) {
      n |= parts[k++] << j;
      j += 24;
      while (j > 7) {
        res[this.pos++] = (n & 0x7f) | 0x80;
        n >>= 7;
        j -= 7;
      }
    }
  
    // Final part, similar to normal packing aside from the initial offset.
    n |= parts[m] << j;
    do {
      res[this.pos] = n & 0x7f;
      n >>= 7;
    } while (n && (res[this.pos++] |= 0x80));
    this.pos++;
  
    // Restore original buffer (could make this optional?).
    if (neg) {
      invert(buf, 8);
    }
  };
  
  // Helpers.
  
  /**
   * Invert all bits in a buffer.
   *
   * @param buf {Buffer} Non-empty buffer to invert.
   * @param len {Number} Buffer length (must be positive).
   */
  function invert(buf, len) {
    while (len--) {
      buf[len] = ~buf[len];
    }
  }
  
  
  module.exports = {
    abstractFunction: abstractFunction,
    addDeprecatedGetters: addDeprecatedGetters,
    capitalize: capitalize,
    copyOwnProperties: copyOwnProperties,
    getHash: getHash,
    compare: compare,
    getOption: getOption,
    jsonEnd: jsonEnd,
    objectValues: objectValues,
    toMap: toMap,
    singleIndexOf: singleIndexOf,
    hasDuplicates: hasDuplicates,
    Lcg: Lcg,
    OrderedQueue: OrderedQueue,
    Tap: Tap
  };
  