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     if ([hashes count] == 0)
  49         return [HashMapHash formatHash:[HashMapHash calculateHash:[NSData dataWithBytes:padding length:0]]];
  50     if ([hashes count] == 1)
  51         return [HashMapHash formatHash:[hashes objectAtIndex:0]];
  52
  53     int s = 2;
  54     while (s < [hashes count])
  55         s = s * 2;
  56
  57     NSMutableArray *h = [NSMutableArray array];
  58     for (int i = 0; i < [hashes count]; i++)
  59         [h addObject:[hashes objectAtIndex:i]];
  60     for (int i = 0; i < s - [hashes count]; i++)
  61         [h addObject:[NSMutableData dataWithBytes:padding length:32]];
  62
  63     while ([h count] > 1) {
  64         for (int i = 0; i < [h count]; i = i + 2) {
  65             NSMutableData *bytesData = [h objectAtIndex:i];
  66             [bytesData appendData:[h objectAtIndex:i + 1]];
  67             [h replaceObjectAtIndex:i withObject:[HashMapHash calculateHash:bytesData]];
  68         }
  69
  70         NSMutableIndexSet *indicesToRemove = [NSMutableIndexSet indexSet];
  71         for (int i = 0; i < [h count]; i = i + 2)
  72             [indicesToRemove addIndex:i + 1];
  73
  74         [h removeObjectsAtIndexes:indicesToRemove];
  75     }
  76     return [HashMapHash formatHash:[h objectAtIndex:0]];
  77 }
  78
  79 + (NSData *)calculateHash:(NSData *)data {
  80     unsigned char hash[CC_SHA256_DIGEST_LENGTH];
  81     CC_SHA256([data bytes], (unsigned int)[data length], hash);
  82     return [NSMutableData dataWithBytes:hash length:CC_SHA256_DIGEST_LENGTH];
  83 }
  84
  85 + (NSString *)formatHash:(NSData *)data {
  86     NSString *hashString;
  87     hashString = [NSString stringWithFormat:@"%@", data];
  88     hashString = [hashString stringByReplacingOccurrencesOfString:@" " withString:@""];
  89     hashString = [hashString stringByTrimmingCharactersInSet:[NSCharacterSet characterSetWithCharactersInString:@"<>"]];
  90     return hashString;
  91 }
  92
  93 // XXX hardcoded hash algorithm for now
  94 + (NSArray *)calculateObjectHashMap:(NSString *)filePath withBlockHash:(NSString *)blockHash andBlockSize:(NSUInteger)blockSize {
  95     NSFileHandle *fh = [NSFileHandle fileHandleForReadingAtPath:filePath];
  96     if (fh == nil) {
  97         NSLog(@"failed to open file: %@", filePath);
  98         return nil;
  99     }
 100
 101     NSFileManager *fm = [NSFileManager defaultManager];
 102     NSDictionary *attributes = [fm attributesOfItemAtPath:filePath error:nil];
 103     NSUInteger endOfFile = [attributes fileSize];
 104
 105     NSUInteger fileOffset = 0;
 106     [fh seekToFileOffset:fileOffset];
 107
 108     NSMutableArray *hashes = [[[NSMutableArray alloc] init] autorelease];
 109
 110     while(fileOffset < endOfFile){
 111         NSData *data = [fh readDataOfLength:blockSize];
 112
 113         // Strip trailing slashes.
 114         const char *bytes = [data bytes];
 115         NSInteger i;
 116         for (i = [data length] - 1; i >= 0; i--)
 117             if (bytes[i] != '\0')
 118                 break;
 119         if (i != [data length] - 1) {
 120             if (i >= 0)
 121                 data = [data subdataWithRange:NSMakeRange(0, i + 1)];
 122             else
 123                 data = [NSData data];
 124         }
 125
 126         unsigned char hash[CC_SHA256_DIGEST_LENGTH];
 127
 128         if ( CC_SHA256([data bytes], (unsigned int)[data length], hash) ) {
 129             NSData *sha256 = [NSMutableData dataWithBytes:hash length:CC_SHA256_DIGEST_LENGTH];
 130             [hashes addObject:sha256];
 131         }
 132
 133         fileOffset += blockSize;
 134         [fh seekToFileOffset:fileOffset];
 135     }
 136
 137     [fh closeFile];
 138
 139     NSArray *hashMap = [NSArray arrayWithArray:hashes];
 140
 141     return hashMap;
 142 }
 143
 144 + (NSArray *)objectHashMapStrings:(NSString *)filePath withBlockHash:(NSString *)blockHash andBlockSize:(NSUInteger)blockSize {
 145     NSArray *hashHexes = [HashMapHash calculateObjectHashMap:filePath withBlockHash:blockHash andBlockSize:blockSize];
 146     if (hashHexes == nil)
 147         return nil;
 148
 149     NSMutableArray *hashStrings = [[[NSMutableArray alloc] init] autorelease];
 150
 151     for (NSData *hashHex in hashHexes) {
 152         [hashStrings addObject:[HashMapHash formatHash:hashHex]];
 153     }
 154
 155     NSArray *hashMap = [NSArray arrayWithArray:hashStrings];
 156     return hashMap;
 157 }
 158
 159 @end