code.grnet.gr Git - pithos-macos/blob - pithos-macos/HashMapHash.m

   1 //
   2 //  HashMapHash.m
   3 //  pithos-macos
   4 //
   5 // Copyright 2011 GRNET S.A. All rights reserved.
   6 //
   7 // Redistribution and use in source and binary forms, with or
   8 // without modification, are permitted provided that the following
   9 // conditions are met:
  10 //
  11 //   1. Redistributions of source code must retain the above
  12 //      copyright notice, this list of conditions and the following
  13 //      disclaimer.
  14 //
  15 //   2. Redistributions in binary form must reproduce the above
  16 //      copyright notice, this list of conditions and the following
  17 //      disclaimer in the documentation and/or other materials
  18 //      provided with the distribution.
  19 //
  20 // THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  21 // OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  22 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  23 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  24 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  26 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  27 // USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  28 // AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31 // POSSIBILITY OF SUCH DAMAGE.
  32 //
  33 // The views and conclusions contained in the software and
  34 // documentation are those of the authors and should not be
  35 // interpreted as representing official policies, either expressed
  36 // or implied, of GRNET S.A.
  37
  38 #import "HashMapHash.h"
  39 #import <CommonCrypto/CommonHMAC.h>
  40
  41 @implementation HashMapHash
  42
  43 + (NSString *)calculateHashMapHash:(NSArray *)hashes {
  44     const char padding[] = {
  45         '\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0',
  46         '\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0','\0'};
  47
  48     NSUInteger hashesCount = [hashes count];
  49     if (hashesCount == 0)
  50         return [self formatHash:[self calculateHash:[NSData data]]];
  51     if (hashesCount == 1)
  52         return [self formatHash:[hashes objectAtIndex:0]];
  53
  54     NSUInteger s = 2;
  55     while (s < hashesCount)
  56         s = s * 2;
  57
  58     NSMutableArray *h = [NSMutableArray arrayWithCapacity:s];
  59     for (NSUInteger i = 0; i < hashesCount; i++)
  60         [h addObject:[hashes objectAtIndex:i]];
  61     for (NSUInteger i = 0; i < s - hashesCount; i++)
  62         [h addObject:[NSMutableData dataWithBytes:padding length:32]];
  63
  64     while ([h count] > 1) {
  65         for (NSUInteger i = 0; i < [h count]; i = i + 2) {
  66             NSMutableData *bytesData = [h objectAtIndex:i];
  67             [bytesData appendData:[h objectAtIndex:i + 1]];
  68             [h replaceObjectAtIndex:i withObject:[self calculateHash:bytesData]];
  69         }
  70
  71         NSMutableIndexSet *indicesToRemove = [NSMutableIndexSet indexSet];
  72         for (int i = 0; i < [h count]; i = i + 2)
  73             [indicesToRemove addIndex:i + 1];
  74
  75         [h removeObjectsAtIndexes:indicesToRemove];
  76     }
  77     return [self formatHash:[h objectAtIndex:0]];
  78 }
  79
  80 + (NSData *)calculateHash:(NSData *)data {
  81     unsigned char hash[CC_SHA256_DIGEST_LENGTH];
  82     CC_SHA256([data bytes], (unsigned int)[data length], hash);
  83     return [NSMutableData dataWithBytes:hash length:CC_SHA256_DIGEST_LENGTH];
  84 }
  85
  86 + (NSString *)formatHash:(NSData *)data {
  87     return [[[NSString stringWithFormat:@"%@", data]
  88              stringByReplacingOccurrencesOfString:@" " withString:@""]
  89             stringByTrimmingCharactersInSet:[NSCharacterSet characterSetWithCharactersInString:@"<>"]];
  90 }
  91
  92 // XXX hardcoded hash algorithm for now
  93 + (NSArray *)calculateObjectHashMap:(NSString *)filePath withBlockHash:(NSString *)blockHash andBlockSize:(NSUInteger)blockSize {
  94     NSFileHandle *fileHandle = [NSFileHandle fileHandleForReadingAtPath:filePath];
  95     if (!fileHandle) {
  96         NSLog(@"HashMapHash failed to open file: %@", filePath);
  97         return nil;
  98     }
  99
 100     NSDictionary *attributes = [[NSFileManager defaultManager] attributesOfItemAtPath:filePath error:nil];
 101     NSUInteger fileSize = [attributes fileSize];
 102     NSMutableArray *hashes = [NSMutableArray arrayWithCapacity:(fileSize/blockSize + 1)];
 103
 104     BOOL done;
 105     while (!done) {
 106         NSAutoreleasePool * pool = [NSAutoreleasePool new];
 107         NSData *data = [fileHandle readDataOfLength:blockSize];
 108         done = ([data length] == 0);
 109
 110         if (!done) {
 111             // Strip trailing slashes.
 112             const char *bytes = [data bytes];
 113             NSInteger i;
 114             for (i = [data length] - 1; i >= 0; i--) {
 115                 if (bytes[i] != '\0')
 116                     break;
 117             }
 118             if (i != [data length] - 1) {
 119                 if (i >= 0)
 120                     data = [data subdataWithRange:NSMakeRange(0, i + 1)];
 121                 else
 122                     data = [NSData data];
 123             }
 124
 125             unsigned char hash[CC_SHA256_DIGEST_LENGTH];
 126             if (CC_SHA256([data bytes], (unsigned int)[data length], hash))
 127                 [hashes addObject:[NSMutableData dataWithBytes:hash length:CC_SHA256_DIGEST_LENGTH]];
 128         }
 129
 130         [pool drain];
 131     }
 132     [fileHandle closeFile];
 133
 134     return [NSArray arrayWithArray:hashes];
 135 }
 136
 137 + (NSArray *)objectHashMapStrings:(NSString *)filePath withBlockHash:(NSString *)blockHash andBlockSize:(NSUInteger)blockSize {
 138     NSArray *hashHexes = [HashMapHash calculateObjectHashMap:filePath withBlockHash:blockHash andBlockSize:blockSize];
 139     if (!hashHexes)
 140         return nil;
 141
 142     NSMutableArray *hashStrings = [NSMutableArray arrayWithCapacity:[hashHexes count]];
 143     for (NSData *hashHex in hashHexes) {
 144         [hashStrings addObject:[self formatHash:hashHex]];
 145     }
 146     return [NSArray arrayWithArray:hashStrings];
 147 }
 148
 149 @end