# BSON MiniHash

Compacts cryptographic hashes and other strings of limited charsets into blobs of BSON binary data, to reduce MongoDB storage and index size. Supports the vanilla Mongo driver, MongoMapper and Mongoid.

## Installation

Add this line to your application's Gemfile:

    gem 'bson_minihash'

And then execute:

    $ bundle

Or install it yourself as:

    $ gem install bson_minihash

## Usage

You need to require either the 'bson' (Mongo driver/MongoMapper) or 'moped' (Mongoid) libraries before using MiniHash, so it knows which library's binary object type to give you. If you're using MongoMapper or Mongoid, one of those libraries has already been loaded for you.

### Digestion

If you've got some data you want to digest, then pack into a minihash, `BSONMiniHash#digest(data, hash_type)` provides a shortcut to do so.

    require 'mongo'
    require 'bson_minihash'
    
    BSONMiniHash.digest("Geddy Lee", :md5)
    #=> <BSON::Binary:70301078819340>

`hash_type` can be either `:md5` or `:sha1`

### Packing pre-existing hashes

If you've already got a hash as a string (e.g. passed as a parameter to your web app), you can pack it into a minihash that's suitable for a `#find` operation by using `BSONMiniHash.pack(string, hash_type)`.

    require 'mongo'
    require 'bson_minihash'
    
    BSONMiniHash.pack('99f815bab7703b220c97feeca3ff9769', :md5)
    #=> <BSON::Binary:70301087948100>

`hash_type` can be `:md5`, `:sha1` or `:hex`

It's best to pass the kind of hash you're using, minihash will do a little validation on the hash to make sure it fits the right character set and length. `:hex` just checks for the hex character range, without a length check, see the Caveats section below before using it.

### Examples

For examples of using minihashes in MongoDB, please see the `examples` direcotry.

## How does it work?

Have you ever wondered what the difference between `Digest::SHA1.digest` and `Digest::SHA1.hexdigest` is?

    str = "Geddy Lee"

    Digest::SHA1.digest(str).length
    #=> 20
    
    Digest::SHA1.hexdigest(str).length
    #=> 40

They both contain the same information, except `#digest` uses only the space that it needs to represent the hash. SHA1 and MD5 both use different length combinations of only sixteen characters (hex) to represent their hashes. A nibble (half a byte, four bits), is enough room to store one of those character.

`#hexdigest` gives a UTF-8 string, which uses a byte per character when relegated to the ASCII range, double the amount needed.

So we convert each character in the hash to its actual hex value:

    Digest::SHA1.hexdigest(str).split('').collect(&:hex)
    #=> [3, 14, 10, 10, 12, 14, 9, 0, 14, 5, 5, 2, 6, 14, 5, 10, 12, 12, 9, 6, 15, 1, 13, 6, 13, 11, 1, 4, 6, 11, 0, 14, 13, 4, 0, 1, 12, 2, 15, 14]

Then pack them together into a new string, treating each number as a nibble:

    Digest::SHA1.hexdigest(str).split('').collect(&:hex).in_groups_of(2).collect{|n| (n.first << 4) + n.last }.pack("C*")
    #=> ">\xAA\xCE\x90\xE5RnZ\xCC\x96\xF1\xD6\xDB\x14k\x0E\xD4\x01\xC2\xFE"
    
That's a roundabout way of emulating `#digest` :)

    Digest::SHA1.digest(str)
    #=> ">\xAA\xCE\x90\xE5RnZ\xCC\x96\xF1\xD6\xDB\x14k\x0E\xD4\x01\xC2\xFE"

Or, we could use the handy "hex" format of `Array#pack`, which is what minihash does.

    [Digest::SHA1.hexdigest(str)].pack('H*')
    # => ">\xAA\xCE\x90\xE5RnZ\xCC\x96\xF1\xD6\xDB\x14k\x0E\xD4\x01\xC2\xFE"

## Efficiency

In MongoDB, you should see about a factor of two space saving for the minihash fields. Of course, you're spending some CPU power to pack the fields, but it's not much.

## Caveats
In MongoDB, it's not a great idea to use hashes as unique indexes, since there's always the possiblity of collisions.

If you choose to `#pack` a string with the `:hex` type, beware that an odd-length string will have an extra nibble at the end, since a byte is the smallest unit of allocation.

## Contributing

1. Fork it
2. Create your feature branch (`git checkout -b my-new-feature`)
3. Commit your changes (`git commit -am 'Add some feature'`)
4. Push to the branch (`git push origin my-new-feature`)
5. Create new Pull Request