1 /*---------------------------------------------------------------------------*
2   Project:  Horizon
3   File:     tpl_crc32.cpp
4 
5   Copyright (C)2009 Nintendo Co., Ltd.  All rights reserved.
6 
7   These coded instructions, statements, and computer programs contain
8   proprietary information of Nintendo of America Inc. and/or Nintendo
9   Company Ltd., and are protected by Federal copyright law.  They may
10   not be disclosed to third parties or copied or duplicated in any form,
11   in whole or in part, without the prior written consent of Nintendo.
12 
13   $Rev: 19746 $
14  *---------------------------------------------------------------------------*/
15 
16 #include <stdlib.h>
17 #include <nn/util.h>
18 #include <nn/tpl.h>
19 #include <cstring>
20 
21 #include "tpl_crc32.h"
22 #include "tpl_Internal.h"
23 
24 namespace nn { namespace tpl { namespace CTR {
25 
26 
27 static const unsigned int _crcTable_[256] =
28 {
29     0x00000000,0x77073096,0xee0e612c,0x990951ba,
30     0x076dc419,0x706af48f,0xe963a535,0x9e6495a3,
31     0x0edb8832,0x79dcb8a4,0xe0d5e91e,0x97d2d988,
32     0x09b64c2b,0x7eb17cbd,0xe7b82d07,0x90bf1d91,
33     0x1db71064,0x6ab020f2,0xf3b97148,0x84be41de,
34     0x1adad47d,0x6ddde4eb,0xf4d4b551,0x83d385c7,
35     0x136c9856,0x646ba8c0,0xfd62f97a,0x8a65c9ec,
36     0x14015c4f,0x63066cd9,0xfa0f3d63,0x8d080df5,
37     0x3b6e20c8,0x4c69105e,0xd56041e4,0xa2677172,
38     0x3c03e4d1,0x4b04d447,0xd20d85fd,0xa50ab56b,
39     0x35b5a8fa,0x42b2986c,0xdbbbc9d6,0xacbcf940,
40     0x32d86ce3,0x45df5c75,0xdcd60dcf,0xabd13d59,
41     0x26d930ac,0x51de003a,0xc8d75180,0xbfd06116,
42     0x21b4f4b5,0x56b3c423,0xcfba9599,0xb8bda50f,
43     0x2802b89e,0x5f058808,0xc60cd9b2,0xb10be924,
44     0x2f6f7c87,0x58684c11,0xc1611dab,0xb6662d3d,
45     0x76dc4190,0x01db7106,0x98d220bc,0xefd5102a,
46     0x71b18589,0x06b6b51f,0x9fbfe4a5,0xe8b8d433,
47     0x7807c9a2,0x0f00f934,0x9609a88e,0xe10e9818,
48     0x7f6a0dbb,0x086d3d2d,0x91646c97,0xe6635c01,
49     0x6b6b51f4,0x1c6c6162,0x856530d8,0xf262004e,
50     0x6c0695ed,0x1b01a57b,0x8208f4c1,0xf50fc457,
51     0x65b0d9c6,0x12b7e950,0x8bbeb8ea,0xfcb9887c,
52     0x62dd1ddf,0x15da2d49,0x8cd37cf3,0xfbd44c65,
53     0x4db26158,0x3ab551ce,0xa3bc0074,0xd4bb30e2,
54     0x4adfa541,0x3dd895d7,0xa4d1c46d,0xd3d6f4fb,
55     0x4369e96a,0x346ed9fc,0xad678846,0xda60b8d0,
56     0x44042d73,0x33031de5,0xaa0a4c5f,0xdd0d7cc9,
57     0x5005713c,0x270241aa,0xbe0b1010,0xc90c2086,
58     0x5768b525,0x206f85b3,0xb966d409,0xce61e49f,
59     0x5edef90e,0x29d9c998,0xb0d09822,0xc7d7a8b4,
60     0x59b33d17,0x2eb40d81,0xb7bd5c3b,0xc0ba6cad,
61     0xedb88320,0x9abfb3b6,0x03b6e20c,0x74b1d29a,
62     0xead54739,0x9dd277af,0x04db2615,0x73dc1683,
63     0xe3630b12,0x94643b84,0x0d6d6a3e,0x7a6a5aa8,
64     0xe40ecf0b,0x9309ff9d,0x0a00ae27,0x7d079eb1,
65     0xf00f9344,0x8708a3d2,0x1e01f268,0x6906c2fe,
66     0xf762575d,0x806567cb,0x196c3671,0x6e6b06e7,
67     0xfed41b76,0x89d32be0,0x10da7a5a,0x67dd4acc,
68     0xf9b9df6f,0x8ebeeff9,0x17b7be43,0x60b08ed5,
69     0xd6d6a3e8,0xa1d1937e,0x38d8c2c4,0x4fdff252,
70     0xd1bb67f1,0xa6bc5767,0x3fb506dd,0x48b2364b,
71     0xd80d2bda,0xaf0a1b4c,0x36034af6,0x41047a60,
72     0xdf60efc3,0xa867df55,0x316e8eef,0x4669be79,
73     0xcb61b38c,0xbc66831a,0x256fd2a0,0x5268e236,
74     0xcc0c7795,0xbb0b4703,0x220216b9,0x5505262f,
75     0xc5ba3bbe,0xb2bd0b28,0x2bb45a92,0x5cb36a04,
76     0xc2d7ffa7,0xb5d0cf31,0x2cd99e8b,0x5bdeae1d,
77     0x9b64c2b0,0xec63f226,0x756aa39c,0x026d930a,
78     0x9c0906a9,0xeb0e363f,0x72076785,0x05005713,
79     0x95bf4a82,0xe2b87a14,0x7bb12bae,0x0cb61b38,
80     0x92d28e9b,0xe5d5be0d,0x7cdcefb7,0x0bdbdf21,
81     0x86d3d2d4,0xf1d4e242,0x68ddb3f8,0x1fda836e,
82     0x81be16cd,0xf6b9265b,0x6fb077e1,0x18b74777,
83     0x88085ae6,0xff0f6a70,0x66063bca,0x11010b5c,
84     0x8f659eff,0xf862ae69,0x616bffd3,0x166ccf45,
85     0xa00ae278,0xd70dd2ee,0x4e048354,0x3903b3c2,
86     0xa7672661,0xd06016f7,0x4969474d,0x3e6e77db,
87     0xaed16a4a,0xd9d65adc,0x40df0b66,0x37d83bf0,
88     0xa9bcae53,0xdebb9ec5,0x47b2cf7f,0x30b5ffe9,
89     0xbdbdf21c,0xcabac28a,0x53b39330,0x24b4a3a6,
90     0xbad03605,0xcdd70693,0x54de5729,0x23d967bf,
91     0xb3667a2e,0xc4614ab8,0x5d681b02,0x2a6f2b94,
92     0xb40bbe37,0xc30c8ea1,0x5a05df1b,0x2d02ef8d,
93 };
94 
95 //----------------------------------------------------------------------------
96 // データブロックに対してCRC32コードを計算する。
calculate_crc32(const void * data,unsigned int size)97 unsigned int calculate_crc32(
98     const void *data,
99     unsigned int size)
100 {
101     unsigned int i;
102     const unsigned char *m = (const unsigned char *)(data);
103     unsigned int crc = 0xffffffff;
104 
105     for(i = 0; i < size; i++)
106     {
107         crc = (crc >> 8) ^ _crcTable_[(crc & 0xFF) ^ (unsigned int)(*m) ];
108         m++;
109     }
110 
111     return crc ^ 0xffffffff;
112 }
113 
114 //----------------------------------------------------------------------------
115 // 先頭にCRC32コードを持つ構造体を検索する。(バイナリサーチ)
search_crc32_index(const void * _base,unsigned int num,unsigned int width,unsigned int crc)116 int search_crc32_index(
117     const void *_base, unsigned int num, unsigned int width, unsigned int crc)
118 {
119     int n = 0;
120     int m = (int)num - 1;
121     const char *base = (const char *)_base;
122 
123     while(n <= m)
124     {
125         int c = (n + m) / 2;
126         unsigned int k = *(const unsigned int *)(base + (width * c));
127 
128         // データのCRCが検索キーと一致したら、同じ値が連続している可能性を
129         // 考慮して同じ値の先頭を探してそのインデックスを返す。
130         if(k == crc)
131         {
132             while(0 < c)
133             {
134                 unsigned int kk = *(const unsigned int *)(base + (width * (c - 1)));
135                 if(kk != crc) break;
136                 c--;
137             }
138             return c;
139         }
140 
141         // データが照準に並んでいることを前提に、検索対象を前半分、後ろ半分
142         // に絞り込んで処理を繰り返す。
143         if(k < crc)
144         {
145             // より大きい値を検索しているの後半を探す。
146             n = c + 1;
147         }
148         else /* if(crc < k) */
149         {
150             // より小さい値を検索しているので前半を探す。
151             m = c - 1;
152         }
153     }
154 
155     // 一致するCRCがなければ-1を返す。
156     return -1;
157 }
158 
159 
160 //----------------------------------------------------------------------------
161 // テクスチャパッケージのメモリイメージからテクスチャのパス文字列を取得。
getTextureFilePath(const void * infoData,int index)162 const char *getTextureFilePath(const void *infoData, int index)
163 {
164     const CtrTexturePackageHeader *header =
165         reinterpret_cast<const CtrTexturePackageHeader *>(infoData);
166     NN_TASSERT_(index < header->numTexture);
167 
168     const CtrTextureInfo *texInfo =
169         reinterpret_cast<const CtrTextureInfo *>(header + 1) + index;
170 
171     const char *szTexPath =
172         reinterpret_cast<const char *>(infoData) + texInfo->filePathOffset;
173 
174     return szTexPath;
175 }
176 
cmpTpkSearchData(const void * data,const void * value)177 int cmpTpkSearchData(const void *data, const void *value)
178 {
179     const CtrTextureHash &hash = *(const CtrTextureHash *)data;
180     const TPK_SEARCH_DATA &s = *(const TPK_SEARCH_DATA *)value;
181 
182     // ヘッダ情報からTPKに記録されているファイル名を取得する。
183     const char *filePath = getTextureFilePath(s.infoData, hash.index);
184 
185     // ファイル名を比較する。
186     return (::std::strncmp(filePath, s.szFileName, s.fileNameLen) == 0)? 1: 0;
187 }
188 
189 //----------------------------------------------------------------------------
190 // 先頭にCRC32コードを持つ構造体を検索する。(バイナリサーチ)
search_crc32_data(const void * _base,unsigned int num,unsigned int width,unsigned int crc,const void * value)191 int search_crc32_data(
192     const void *_base, unsigned int num, unsigned int width, unsigned int crc,
193     const void *value)
194 {
195     const char *base = (const char *)_base;
196 
197     // まずはCRC32コードでインデックスを検索する。
198     // この時点で候補がなければ-1を返して終わる。
199     int t = search_crc32_index(_base, num, width, crc);
200     if(t < 0) return -1;
201 
202     // 同じCRC32コードが複数並んでいる可能性があるので、CRC32コードが
203     // 一致する範囲でデータの比較を行う。
204     for(; t < (int)num; t++)
205     {
206         // CRC32コードが異なれば一致無し。
207         const unsigned int *k = (const unsigned int *)(base + (width * t));
208         if(*k != crc) return -1;
209 
210         // 比較関数を用いてデータが本当に検索対象であるか調べる。
211         if(cmpTpkSearchData((const void*)k, value) != 0)
212         {
213             return t;
214         }
215     }
216     return -1;
217 }
218 
219 
220 }}} // namespace
221