Fix splitting of cells (noticed by Hartmut).
[reactos.git] / reactos / tools / mkhive / binhive.c
1 /*
2 * ReactOS kernel
3 * Copyright (C) 2003, 2004 ReactOS Team
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19 /* $Id$
20 * COPYRIGHT: See COPYING in the top level directory
21 * PROJECT: ReactOS hive maker
22 * FILE: tools/mkhive/binhive.c
23 * PURPOSE: Binary hive export code
24 * PROGRAMMER: Eric Kohl
25 */
26
27 /* INCLUDES *****************************************************************/
28
29 //#include <assert.h>
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <string.h>
33
34 #include "mkhive.h"
35 #include "binhive.h"
36 #include "registry.h"
37
38
39 #define REG_HIVE_ID 0x66676572
40 #define REG_BIN_ID 0x6e696268
41 #define REG_KEY_CELL_ID 0x6b6e
42 #define REG_HASH_TABLE_CELL_ID 0x666c
43 #define REG_VALUE_CELL_ID 0x6b76
44
45 #define REG_BLOCK_SIZE 4096
46 #define REG_HBIN_DATA_OFFSET 32
47 #define REG_INIT_BLOCK_LIST_SIZE 32
48 #define REG_INIT_HASH_TABLE_SIZE 3
49 #define REG_EXTEND_HASH_TABLE_SIZE 4
50 #define REG_VALUE_LIST_CELL_MULTIPLE 4
51
52 #define ROUND_UP_POW2(N,S) (((N) + (S) - 1) & ~((S) - 1))
53 #define ROUND_DOWN_POW2(N,S) ((N) & ~((S) - 1))
54
55 #define ABS_VALUE(V) (((V) < 0) ? -(V) : (V))
56
57
58 // BLOCK_OFFSET = offset in file after header block
59 typedef ULONG BLOCK_OFFSET, *PBLOCK_OFFSET;
60
61 #ifdef _MSC_VER
62 typedef unsigned __int64 FILETIME;
63 #else
64 typedef unsigned long long FILETIME;
65 #endif
66
67 #ifdef _MSC_VER
68 #pragma pack ( push, hive_header, 1 )
69 #endif//_MSC_VER
70
71 /* header for registry hive file : */
72 typedef struct _HIVE_HEADER
73 {
74 /* Hive identifier "regf" (0x66676572) */
75 ULONG BlockId;
76
77 /* Update counter */
78 ULONG UpdateCounter1;
79
80 /* Update counter */
81 ULONG UpdateCounter2;
82
83 /* When this hive file was last modified */
84 FILETIME DateModified;
85
86 /* Registry format major version (1) */
87 ULONG MajorVersion;
88
89 /* Registry format minor version (3)
90 Version 3 added fast indexes, version 5 has large value optimizations */
91 ULONG MinorVersion;
92
93 /* Registry file type (0 - Primary, 1 - Log) */
94 ULONG Type;
95
96 /* Registry format (1 is the only defined value so far) */
97 ULONG Format;
98
99 /* Offset into file from the byte after the end of the base block.
100 If the hive is volatile, this is the actual pointer to the KEY_CELL */
101 BLOCK_OFFSET RootKeyOffset;
102
103 /* Size of each hive block ? */
104 ULONG BlockSize;
105
106 /* (1?) */
107 ULONG Unused7;
108
109 /* Name of hive file */
110 WCHAR FileName[48];
111
112 ULONG Reserved[99];
113
114 /* Checksum of first 0x200 bytes */
115 ULONG Checksum;
116 } GCC_PACKED HIVE_HEADER, *PHIVE_HEADER;
117
118 typedef struct _HBIN
119 {
120 /* Bin identifier "hbin" (0x6E696268) */
121 ULONG HeaderId;
122
123 /* Block offset of this bin */
124 BLOCK_OFFSET BinOffset;
125
126 /* Size in bytes, multiple of the block size (4KB) */
127 ULONG BinSize;
128
129 ULONG Reserved[2];
130
131 /* When this bin was last modified */
132 FILETIME DateModified;
133
134 /* ? (In-memory only) */
135 ULONG MemAlloc;
136 } GCC_PACKED HBIN, *PHBIN;
137
138 typedef struct _CELL_HEADER
139 {
140 /* <0 if used, >0 if free */
141 LONG CellSize;
142 } GCC_PACKED CELL_HEADER, *PCELL_HEADER;
143
144 typedef struct _KEY_CELL
145 {
146 /* Size of this cell */
147 LONG CellSize;
148
149 /* Key cell identifier "kn" (0x6b6e) */
150 USHORT Id;
151
152 /* ? */
153 USHORT Type;
154
155 /* Time of last flush */
156 FILETIME LastWriteTime;
157
158 /* ? */
159 ULONG UnUsed1;
160
161 /* Block offset of parent key cell */
162 BLOCK_OFFSET ParentKeyOffset;
163
164 /* Count of sub keys for the key in this key cell */
165 ULONG NumberOfSubKeys;
166
167 /* ? */
168 ULONG UnUsed2;
169
170 /* Block offset of has table for FIXME: subkeys/values? */
171 BLOCK_OFFSET HashTableOffset;
172
173 /* ? */
174 ULONG UnUsed3;
175
176 /* Count of values contained in this key cell */
177 ULONG NumberOfValues;
178
179 /* Block offset of VALUE_LIST_CELL */
180 BLOCK_OFFSET ValueListOffset;
181
182 /* Block offset of security cell */
183 BLOCK_OFFSET SecurityKeyOffset;
184
185 /* Block offset of registry key class */
186 BLOCK_OFFSET ClassNameOffset;
187
188 /* ? */
189 ULONG Unused4[5];
190
191 /* Size in bytes of key name */
192 USHORT NameSize;
193
194 /* Size of class name in bytes */
195 USHORT ClassSize;
196
197 /* Name of key (not zero terminated) */
198 CHAR Name[0];
199 } GCC_PACKED KEY_CELL, *PKEY_CELL;
200
201 /* KEY_CELL.Type constants */
202 #define REG_LINK_KEY_CELL_TYPE 0x10
203 #define REG_KEY_CELL_TYPE 0x20
204 #define REG_ROOT_KEY_CELL_TYPE 0x2c
205
206
207 // hash record :
208 // HashValue=four letters of value's name
209 typedef struct _HASH_RECORD
210 {
211 BLOCK_OFFSET KeyOffset;
212 ULONG HashValue;
213 } GCC_PACKED HASH_RECORD, *PHASH_RECORD;
214
215 typedef struct _HASH_TABLE_CELL
216 {
217 LONG CellSize;
218 USHORT Id;
219 USHORT HashTableSize;
220 HASH_RECORD Table[0];
221 } GCC_PACKED HASH_TABLE_CELL, *PHASH_TABLE_CELL;
222
223 typedef struct _VALUE_LIST_CELL
224 {
225 LONG CellSize;
226 BLOCK_OFFSET ValueOffset[0];
227 } GCC_PACKED VALUE_LIST_CELL, *PVALUE_LIST_CELL;
228
229 typedef struct _VALUE_CELL
230 {
231 LONG CellSize;
232 USHORT Id; // "kv"
233 USHORT NameSize; // length of Name
234 ULONG DataSize; // length of datas in the cell pointed by DataOffset
235 BLOCK_OFFSET DataOffset;// datas are here if high bit of DataSize is set
236 ULONG DataType;
237 USHORT Flags;
238 USHORT Unused1;
239 CHAR Name[0]; /* warning : not zero terminated */
240 } GCC_PACKED VALUE_CELL, *PVALUE_CELL;
241
242 /* VALUE_CELL.Flags constants */
243 #define REG_VALUE_NAME_PACKED 0x0001
244
245 /* VALUE_CELL.DataSize mask constants */
246 #define REG_DATA_SIZE_MASK 0x7FFFFFFF
247 #define REG_DATA_IN_OFFSET 0x80000000
248
249 typedef struct _DATA_CELL
250 {
251 LONG CellSize;
252 CHAR Data[0];
253 } GCC_PACKED DATA_CELL, *PDATA_CELL;
254
255 #ifdef _MSC_VER
256 #pragma pack ( pop, hive_header )
257 #endif//_MSC_VER
258
259 typedef struct _REGISTRY_HIVE
260 {
261 ULONG FileSize;
262 PHIVE_HEADER HiveHeader;
263 ULONG BlockListSize;
264 PHBIN *BlockList;
265 ULONG FreeListSize;
266 ULONG FreeListMax;
267 PCELL_HEADER *FreeList;
268 BLOCK_OFFSET *FreeListOffset;
269 } REGISTRY_HIVE, *PREGISTRY_HIVE;
270
271 /* FUNCTIONS ****************************************************************/
272
273 static VOID
274 memexpand (PWCHAR Dst,
275 PCHAR Src,
276 ULONG Length)
277 {
278 ULONG i;
279
280 for (i = 0; i < Length; i++)
281 Dst[i] = (WCHAR)Src[i];
282 }
283
284
285 static VOID
286 CmiCreateDefaultHiveHeader (PHIVE_HEADER Header)
287 {
288 assert (Header);
289 memset (Header, 0, REG_BLOCK_SIZE);
290 Header->BlockId = REG_HIVE_ID;
291 Header->UpdateCounter1 = 0;
292 Header->UpdateCounter2 = 0;
293 Header->DateModified = 0;
294 Header->MajorVersion = 1;
295 Header->MinorVersion = 3;
296 Header->Type = 0;
297 Header->Format = 1;
298 Header->Unused7 = 1;
299 Header->RootKeyOffset = -1;
300 Header->BlockSize = REG_BLOCK_SIZE;
301 Header->Checksum = 0;
302 }
303
304
305 static VOID
306 CmiCreateDefaultBinCell(PHBIN BinCell)
307 {
308 assert (BinCell);
309 memset (BinCell, 0, REG_BLOCK_SIZE);
310 BinCell->HeaderId = REG_BIN_ID;
311 BinCell->DateModified = 0;
312 BinCell->BinSize = REG_BLOCK_SIZE;
313 }
314
315
316 static VOID
317 CmiCreateDefaultRootKeyCell(PKEY_CELL RootKeyCell, PCHAR KeyName)
318 {
319 PCHAR BaseKeyName;
320 USHORT NameSize;
321 ULONG CellSize;
322
323 assert (RootKeyCell);
324
325 BaseKeyName = strrchr(KeyName, '\\') + 1;
326 NameSize = strlen(BaseKeyName);
327 CellSize = ROUND_UP_POW2(sizeof(KEY_CELL) + NameSize - 1, 16);
328
329 memset (RootKeyCell, 0, CellSize);
330 RootKeyCell->CellSize = (ULONG)-(LONG)CellSize;
331 RootKeyCell->Id = REG_KEY_CELL_ID;
332 RootKeyCell->Type = REG_ROOT_KEY_CELL_TYPE;
333 RootKeyCell->LastWriteTime = 0;
334 RootKeyCell->ParentKeyOffset = 0;
335 RootKeyCell->NumberOfSubKeys = 0;
336 RootKeyCell->HashTableOffset = -1;
337 RootKeyCell->NumberOfValues = 0;
338 RootKeyCell->ValueListOffset = -1;
339 RootKeyCell->SecurityKeyOffset = 0;
340 RootKeyCell->ClassNameOffset = -1;
341 RootKeyCell->NameSize = NameSize;
342 RootKeyCell->ClassSize = 0;
343 memcpy (RootKeyCell->Name,
344 BaseKeyName,
345 NameSize);
346 }
347
348
349 static PREGISTRY_HIVE
350 CmiCreateRegistryHive (PCHAR KeyName)
351 {
352 PREGISTRY_HIVE Hive;
353 PCELL_HEADER FreeCell;
354 PKEY_CELL RootKeyCell;
355 PHBIN BinCell;
356
357 Hive = (PREGISTRY_HIVE) malloc (sizeof(REGISTRY_HIVE));
358 if (Hive == NULL)
359 {
360 return NULL;
361 }
362 memset (Hive, 0, sizeof(REGISTRY_HIVE));
363
364 DPRINT("Hive %p\n", Hive);
365
366 /* Create hive beader (aka 'base block') */
367 Hive->HiveHeader = (PHIVE_HEADER) malloc (REG_BLOCK_SIZE);
368 if (Hive->HiveHeader == NULL)
369 {
370 free (Hive);
371 return NULL;
372 }
373 CmiCreateDefaultHiveHeader (Hive->HiveHeader);
374 Hive->FileSize = REG_BLOCK_SIZE;
375
376 /* Allocate block list */
377 Hive->BlockListSize = 1;
378 Hive->BlockList = malloc (sizeof(PHBIN) * Hive->BlockListSize);
379 if (Hive->BlockList == NULL)
380 {
381 free (Hive->HiveHeader);
382 free (Hive);
383 return NULL;
384 }
385
386 /* Allocate free cell list */
387 Hive->FreeListMax = 32;
388 Hive->FreeList = malloc(sizeof(PCELL_HEADER) * Hive->FreeListMax);
389 if (Hive->FreeList == NULL)
390 {
391 free (Hive->BlockList);
392 free (Hive->HiveHeader);
393 free (Hive);
394 return NULL;
395 }
396 Hive->FreeListOffset = malloc(sizeof(BLOCK_OFFSET) * Hive->FreeListMax);
397 if (Hive->FreeListOffset == NULL)
398 {
399 free (Hive->FreeList);
400 free (Hive->BlockList);
401 free (Hive->HiveHeader);
402 free (Hive);
403 return NULL;
404 }
405
406 /* Allocate first bin */
407 Hive->BlockList[0] = (PHBIN) malloc (REG_BLOCK_SIZE);
408 if (Hive->BlockList[0] == NULL)
409 {
410 free (Hive->FreeListOffset);
411 free (Hive->FreeList);
412 free (Hive->BlockList);
413 free (Hive->HiveHeader);
414 free (Hive);
415 return NULL;
416 }
417 Hive->FileSize += REG_BLOCK_SIZE;
418
419 /* Init first bin */
420 BinCell = (PHBIN)Hive->BlockList[0];
421 CmiCreateDefaultBinCell (BinCell);
422 BinCell->BinOffset = 0;
423
424 /* Init root key cell */
425 RootKeyCell = (PKEY_CELL)((ULONG_PTR)BinCell + REG_HBIN_DATA_OFFSET);
426 CmiCreateDefaultRootKeyCell (RootKeyCell, KeyName);
427 Hive->HiveHeader->RootKeyOffset = REG_HBIN_DATA_OFFSET;
428
429 /* Init free cell */
430 FreeCell = (PCELL_HEADER)((ULONG_PTR)RootKeyCell - RootKeyCell->CellSize);
431 FreeCell->CellSize = REG_BLOCK_SIZE - (REG_HBIN_DATA_OFFSET - RootKeyCell->CellSize);
432
433 Hive->FreeList[0] = FreeCell;
434 Hive->FreeListOffset[0] = REG_HBIN_DATA_OFFSET - RootKeyCell->CellSize;
435 Hive->FreeListSize++;
436
437 return Hive;
438 }
439
440
441 static VOID
442 CmiDestroyRegistryHive (PREGISTRY_HIVE Hive)
443 {
444 PHBIN Bin;
445 ULONG i;
446
447 if (Hive == NULL)
448 return;
449
450 /* Release free offset list */
451 if (Hive->FreeListOffset != NULL)
452 free (Hive->FreeListOffset);
453
454 /* Release free list */
455 if (Hive->FreeList != NULL)
456 free (Hive->FreeList);
457
458 if (Hive->BlockList != NULL)
459 {
460 /* Release bins */
461 Bin = NULL;
462 for (i = 0; i < Hive->BlockListSize; i++)
463 {
464 if ((Hive->BlockList[i] != NULL) &&
465 (Hive->BlockList[i] != Bin))
466 {
467 Bin = Hive->BlockList[i];
468
469 DPRINT ("Bin[%lu]: Offset 0x%lx Size 0x%lx\n",
470 i, Bin->BinOffset, Bin->BinSize);
471
472 free (Bin);
473 }
474 }
475
476 /* Release block list */
477 free (Hive->BlockList);
478 }
479
480 /* Release hive header */
481 if (Hive->HiveHeader != NULL)
482 free (Hive->HiveHeader);
483
484 /* Release hive */
485 free (Hive);
486 }
487
488
489 static PVOID
490 CmiGetCell (PREGISTRY_HIVE Hive,
491 BLOCK_OFFSET BlockOffset,
492 PHBIN * ppBin)
493 {
494 PHBIN pBin;
495 ULONG BlockIndex;
496
497 if (ppBin)
498 *ppBin = NULL;
499
500 if (BlockOffset == (ULONG_PTR) -1)
501 return NULL;
502
503 BlockIndex = BlockOffset / 4096;
504 if (BlockIndex >= Hive->BlockListSize)
505 return NULL;
506
507 pBin = Hive->BlockList[BlockIndex];
508 if (ppBin)
509 *ppBin = pBin;
510
511 return (PVOID)((ULONG_PTR)pBin + (BlockOffset - pBin->BinOffset));
512 }
513
514
515 static BOOL
516 CmiMergeFree(PREGISTRY_HIVE RegistryHive,
517 PCELL_HEADER FreeBlock,
518 BLOCK_OFFSET FreeOffset)
519 {
520 BLOCK_OFFSET BlockOffset;
521 BLOCK_OFFSET BinOffset;
522 ULONG BlockSize;
523 ULONG BinSize;
524 PHBIN Bin;
525 ULONG i;
526
527 DPRINT("CmiMergeFree(Block %p Offset %lx Size %lx) called\n",
528 FreeBlock, FreeOffset, FreeBlock->CellSize);
529
530 CmiGetCell (RegistryHive,
531 FreeOffset,
532 &Bin);
533 DPRINT("Bin %p\n", Bin);
534 if (Bin == NULL)
535 return FALSE;
536
537 BinOffset = Bin->BinOffset;
538 BinSize = Bin->BinSize;
539 DPRINT("Bin %p Offset %lx Size %lx\n", Bin, BinOffset, BinSize);
540
541 for (i = 0; i < RegistryHive->FreeListSize; i++)
542 {
543 BlockOffset = RegistryHive->FreeListOffset[i];
544 BlockSize = RegistryHive->FreeList[i]->CellSize;
545 if (BlockOffset > BinOffset &&
546 BlockOffset < BinOffset + BinSize)
547 {
548 DPRINT("Free block: Offset %lx Size %lx\n",
549 BlockOffset, BlockSize);
550
551 if ((i < (RegistryHive->FreeListSize - 1)) &&
552 (BlockOffset + BlockSize == FreeOffset) &&
553 (FreeOffset + FreeBlock->CellSize == RegistryHive->FreeListOffset[i + 1]))
554 {
555 DPRINT("Merge current block with previous and next block\n");
556
557 RegistryHive->FreeList[i]->CellSize +=
558 (FreeBlock->CellSize + RegistryHive->FreeList[i + 1]->CellSize);
559
560 FreeBlock->CellSize = 0;
561 RegistryHive->FreeList[i + 1]->CellSize = 0;
562
563
564 if ((i + 2) < RegistryHive->FreeListSize)
565 {
566 memmove (&RegistryHive->FreeList[i + 1],
567 &RegistryHive->FreeList[i + 2],
568 sizeof(RegistryHive->FreeList[0])
569 * (RegistryHive->FreeListSize - i - 2));
570 memmove (&RegistryHive->FreeListOffset[i + 1],
571 &RegistryHive->FreeListOffset[i + 2],
572 sizeof(RegistryHive->FreeListOffset[0])
573 * (RegistryHive->FreeListSize - i - 2));
574 }
575 RegistryHive->FreeListSize--;
576
577 return TRUE;
578 }
579 else if (BlockOffset + BlockSize == FreeOffset)
580 {
581 DPRINT("Merge current block with previous block\n");
582
583 RegistryHive->FreeList[i]->CellSize += FreeBlock->CellSize;
584 FreeBlock->CellSize = 0;
585
586 return TRUE;
587 }
588 else if (FreeOffset + FreeBlock->CellSize == BlockOffset)
589 {
590 DPRINT("Merge current block with next block\n");
591
592 FreeBlock->CellSize += RegistryHive->FreeList[i]->CellSize;
593 RegistryHive->FreeList[i]->CellSize = 0;
594 RegistryHive->FreeList[i] = FreeBlock;
595 RegistryHive->FreeListOffset[i] = FreeOffset;
596
597 return TRUE;
598 }
599 }
600 }
601
602 return FALSE;
603 }
604
605
606 static BOOL
607 CmiAddFree(PREGISTRY_HIVE RegistryHive,
608 PCELL_HEADER FreeBlock,
609 BLOCK_OFFSET FreeOffset,
610 BOOL MergeFreeBlocks)
611 {
612 PCELL_HEADER *tmpList;
613 BLOCK_OFFSET *tmpListOffset;
614 LONG minInd;
615 LONG maxInd;
616 LONG medInd;
617
618 assert(RegistryHive);
619 assert(FreeBlock);
620
621 DPRINT("FreeBlock %p FreeOffset %.08lx\n",
622 FreeBlock, FreeOffset);
623
624 /* Merge free blocks */
625 if (MergeFreeBlocks == TRUE)
626 {
627 if (CmiMergeFree(RegistryHive, FreeBlock, FreeOffset))
628 return TRUE;
629 }
630
631 if ((RegistryHive->FreeListSize + 1) > RegistryHive->FreeListMax)
632 {
633 tmpList = malloc (sizeof(PCELL_HEADER) * (RegistryHive->FreeListMax + 32));
634 if (tmpList == NULL)
635 {
636 return FALSE;
637 }
638
639 tmpListOffset = malloc (sizeof(BLOCK_OFFSET) * (RegistryHive->FreeListMax + 32));
640 if (tmpListOffset == NULL)
641 {
642 free (tmpList);
643 return FALSE;
644 }
645
646 if (RegistryHive->FreeListMax)
647 {
648 memmove (tmpList,
649 RegistryHive->FreeList,
650 sizeof(PCELL_HEADER) * (RegistryHive->FreeListMax));
651 memmove (tmpListOffset,
652 RegistryHive->FreeListOffset,
653 sizeof(BLOCK_OFFSET) * (RegistryHive->FreeListMax));
654 free (RegistryHive->FreeList);
655 free (RegistryHive->FreeListOffset);
656 }
657 RegistryHive->FreeList = tmpList;
658 RegistryHive->FreeListOffset = tmpListOffset;
659 RegistryHive->FreeListMax += 32;
660 }
661
662 /* Add new offset to free list, maintaining list in ascending order */
663 if ((RegistryHive->FreeListSize == 0)
664 || (RegistryHive->FreeListOffset[RegistryHive->FreeListSize-1] < FreeOffset))
665 {
666 /* Add to end of list */
667 RegistryHive->FreeList[RegistryHive->FreeListSize] = FreeBlock;
668 RegistryHive->FreeListOffset[RegistryHive->FreeListSize++] = FreeOffset;
669 }
670 else if (RegistryHive->FreeListOffset[0] > FreeOffset)
671 {
672 /* Add to begin of list */
673 memmove (&RegistryHive->FreeList[1],
674 &RegistryHive->FreeList[0],
675 sizeof(RegistryHive->FreeList[0]) * RegistryHive->FreeListSize);
676 memmove (&RegistryHive->FreeListOffset[1],
677 &RegistryHive->FreeListOffset[0],
678 sizeof(RegistryHive->FreeListOffset[0]) * RegistryHive->FreeListSize);
679 RegistryHive->FreeList[0] = FreeBlock;
680 RegistryHive->FreeListOffset[0] = FreeOffset;
681 RegistryHive->FreeListSize++;
682 }
683 else
684 {
685 /* Search where to insert */
686 minInd = 0;
687 maxInd = RegistryHive->FreeListSize - 1;
688 while ((maxInd - minInd) > 1)
689 {
690 medInd = (minInd + maxInd) / 2;
691 if (RegistryHive->FreeListOffset[medInd] > FreeOffset)
692 maxInd = medInd;
693 else
694 minInd = medInd;
695 }
696
697 /* Insert before maxInd */
698 memmove (&RegistryHive->FreeList[maxInd+1],
699 &RegistryHive->FreeList[maxInd],
700 sizeof(RegistryHive->FreeList[0]) * (RegistryHive->FreeListSize - minInd));
701 memmove (&RegistryHive->FreeListOffset[maxInd + 1],
702 &RegistryHive->FreeListOffset[maxInd],
703 sizeof(RegistryHive->FreeListOffset[0]) * (RegistryHive->FreeListSize-minInd));
704 RegistryHive->FreeList[maxInd] = FreeBlock;
705 RegistryHive->FreeListOffset[maxInd] = FreeOffset;
706 RegistryHive->FreeListSize++;
707 }
708
709 return TRUE;
710 }
711
712
713 static BOOL
714 CmiAddBin(PREGISTRY_HIVE RegistryHive,
715 ULONG BlockCount,
716 PVOID *NewBlock,
717 PBLOCK_OFFSET NewBlockOffset)
718 {
719 PCELL_HEADER tmpBlock;
720 PHBIN * tmpBlockList;
721 PHBIN tmpBin;
722 ULONG BinSize;
723 ULONG i;
724
725 BinSize = BlockCount *REG_BLOCK_SIZE;
726 tmpBin = malloc (BinSize);
727 if (tmpBin == NULL)
728 {
729 return FALSE;
730 }
731 memset (tmpBin, 0, BinSize);
732
733 tmpBin->HeaderId = REG_BIN_ID;
734 tmpBin->BinOffset = RegistryHive->FileSize - REG_BLOCK_SIZE;
735 RegistryHive->FileSize += BinSize;
736 tmpBin->BinSize = BinSize;
737 tmpBin->DateModified = 0;
738 tmpBin->MemAlloc = 0;
739
740 /* Increase size of list of blocks */
741 tmpBlockList = malloc (sizeof(PHBIN) * (RegistryHive->BlockListSize + BlockCount));
742 if (tmpBlockList == NULL)
743 {
744 free (tmpBin);
745 return FALSE;
746 }
747
748 if (RegistryHive->BlockListSize > 0)
749 {
750 memcpy (tmpBlockList,
751 RegistryHive->BlockList,
752 sizeof(PHBIN) * RegistryHive->BlockListSize);
753 free (RegistryHive->BlockList);
754 }
755
756 RegistryHive->BlockList = tmpBlockList;
757 for (i = 0; i < BlockCount; i++)
758 RegistryHive->BlockList[RegistryHive->BlockListSize + i] = tmpBin;
759 RegistryHive->BlockListSize += BlockCount;
760
761 /* Initialize a free block in this heap : */
762 tmpBlock = (PCELL_HEADER)((ULONG_PTR) tmpBin + REG_HBIN_DATA_OFFSET);
763 tmpBlock->CellSize = (REG_BLOCK_SIZE - REG_HBIN_DATA_OFFSET);
764
765 *NewBlock = (PVOID) tmpBlock;
766
767 if (NewBlockOffset)
768 *NewBlockOffset = tmpBin->BinOffset + REG_HBIN_DATA_OFFSET;
769
770 return TRUE;
771 }
772
773
774 static BOOL
775 CmiAllocateCell (PREGISTRY_HIVE RegistryHive,
776 LONG CellSize,
777 PVOID *Block,
778 PBLOCK_OFFSET pBlockOffset)
779 {
780 PCELL_HEADER NewBlock;
781 ULONG i;
782
783 *Block = NULL;
784
785 /* Round to 16 bytes multiple */
786 CellSize = ROUND_UP_POW2(CellSize, 16);
787
788 /* first search in free blocks */
789 NewBlock = NULL;
790 for (i = 0; i < RegistryHive->FreeListSize; i++)
791 {
792 if (RegistryHive->FreeList[i]->CellSize >= CellSize)
793 {
794 NewBlock = RegistryHive->FreeList[i];
795 if (pBlockOffset)
796 *pBlockOffset = RegistryHive->FreeListOffset[i];
797
798 if ((i + 1) < RegistryHive->FreeListSize)
799 {
800 memmove (&RegistryHive->FreeList[i],
801 &RegistryHive->FreeList[i + 1],
802 sizeof(RegistryHive->FreeList[0])
803 * (RegistryHive->FreeListSize - i - 1));
804 memmove (&RegistryHive->FreeListOffset[i],
805 &RegistryHive->FreeListOffset[i + 1],
806 sizeof(RegistryHive->FreeListOffset[0])
807 * (RegistryHive->FreeListSize - i - 1));
808 }
809 RegistryHive->FreeListSize--;
810 break;
811 }
812 }
813
814 /* Need to extend hive file : */
815 if (NewBlock == NULL)
816 {
817 /* Add a new block */
818 if (!CmiAddBin(RegistryHive,
819 ((sizeof(HBIN) + CellSize - 1) / REG_BLOCK_SIZE) + 1,
820 (PVOID *)&NewBlock,
821 pBlockOffset))
822 return FALSE;
823 }
824
825 *Block = NewBlock;
826
827 /* Split the block in two parts */
828 if (NewBlock->CellSize > CellSize)
829 {
830 NewBlock = (PCELL_HEADER) ((ULONG_PTR) NewBlock + CellSize);
831 NewBlock->CellSize = ((PCELL_HEADER) (*Block))->CellSize - CellSize;
832 ((PCELL_HEADER) (*Block))->CellSize = CellSize;
833 CmiAddFree (RegistryHive,
834 NewBlock,
835 *pBlockOffset + CellSize,
836 TRUE);
837 }
838 else if (NewBlock->CellSize < CellSize)
839 {
840 return FALSE;
841 }
842
843 memset(*Block, 0, CellSize);
844 ((PCELL_HEADER)(*Block))->CellSize *= -1;
845
846 return TRUE;
847 }
848
849
850 static BOOL
851 CmiAllocateHashTableCell (PREGISTRY_HIVE Hive,
852 PBLOCK_OFFSET HBOffset,
853 USHORT SubKeyCount)
854 {
855 PHASH_TABLE_CELL HashCell;
856 ULONG NewHashSize;
857 BOOL Status;
858
859 NewHashSize = sizeof(HASH_TABLE_CELL) +
860 (SubKeyCount * sizeof(HASH_RECORD));
861 Status = CmiAllocateCell (Hive,
862 NewHashSize,
863 (PVOID*) &HashCell,
864 HBOffset);
865 if ((HashCell == NULL) || (Status == FALSE))
866 {
867 return FALSE;
868 }
869
870 HashCell->Id = REG_HASH_TABLE_CELL_ID;
871 HashCell->HashTableSize = SubKeyCount;
872
873 return TRUE;
874 }
875
876
877 static BOOL
878 CmiAddKeyToParentHashTable (PREGISTRY_HIVE Hive,
879 BLOCK_OFFSET ParentKeyOffset,
880 PKEY_CELL NewKeyCell,
881 BLOCK_OFFSET NKBOffset)
882 {
883 PHASH_TABLE_CELL HashBlock;
884 PKEY_CELL ParentKeyCell;
885 ULONG i;
886
887 ParentKeyCell = CmiGetCell (Hive,
888 ParentKeyOffset,
889 NULL);
890 if (ParentKeyCell == NULL)
891 {
892 DPRINT1 ("CmiGetBlock() failed\n");
893 return FALSE;
894 }
895
896 HashBlock =CmiGetCell (Hive,
897 ParentKeyCell->HashTableOffset,
898 NULL);
899 if (HashBlock == NULL)
900 {
901 DPRINT1 ("CmiGetBlock() failed\n");
902 return FALSE;
903 }
904
905 for (i = 0; i < HashBlock->HashTableSize; i++)
906 {
907 if (HashBlock->Table[i].KeyOffset == 0)
908 {
909 HashBlock->Table[i].KeyOffset = NKBOffset;
910 memcpy (&HashBlock->Table[i].HashValue,
911 NewKeyCell->Name,
912 4);
913 ParentKeyCell->NumberOfSubKeys++;
914 return TRUE;
915 }
916 }
917
918 return FALSE;
919 }
920
921
922 static BOOL
923 CmiAllocateValueListCell (PREGISTRY_HIVE Hive,
924 PBLOCK_OFFSET ValueListOffset,
925 ULONG ValueCount)
926 {
927 PVALUE_LIST_CELL ValueListCell;
928 ULONG ValueListSize;
929 BOOL Status;
930
931 ValueListSize = sizeof(VALUE_LIST_CELL) +
932 (ValueCount * sizeof(BLOCK_OFFSET));
933 Status = CmiAllocateCell (Hive,
934 ValueListSize,
935 (PVOID)&ValueListCell,
936 ValueListOffset);
937 if ((ValueListCell == NULL) || (Status == FALSE))
938 {
939 DPRINT1 ("CmiAllocateBlock() failed\n");
940 return FALSE;
941 }
942
943 return TRUE;
944 }
945
946
947 static BOOL
948 CmiAllocateValueCell(PREGISTRY_HIVE Hive,
949 PVALUE_CELL *ValueCell,
950 BLOCK_OFFSET *ValueCellOffset,
951 PCHAR ValueName)
952 {
953 PVALUE_CELL NewValueCell;
954 USHORT NameSize;
955 BOOL Status;
956
957 NameSize = (ValueName == NULL) ? 0 : strlen (ValueName);
958 Status = CmiAllocateCell (Hive,
959 sizeof(VALUE_CELL) + NameSize,
960 (PVOID*)&NewValueCell,
961 ValueCellOffset);
962 if ((NewValueCell == NULL) || (Status == FALSE))
963 {
964 DPRINT1 ("CmiAllocateBlock() failed\n");
965 return FALSE;
966 }
967
968 NewValueCell->Id = REG_VALUE_CELL_ID;
969 NewValueCell->NameSize = NameSize;
970 if (NameSize > 0)
971 {
972 memcpy (NewValueCell->Name,
973 ValueName,
974 NameSize);
975 NewValueCell->Flags = REG_VALUE_NAME_PACKED;
976 }
977 NewValueCell->DataType = 0;
978 NewValueCell->DataSize = 0;
979 NewValueCell->DataOffset = -1;
980
981 *ValueCell = NewValueCell;
982
983 return TRUE;
984 }
985
986
987 static BOOL
988 CmiAddValueToKeyValueList(PREGISTRY_HIVE Hive,
989 BLOCK_OFFSET KeyCellOffset,
990 BLOCK_OFFSET ValueCellOffset)
991 {
992 PVALUE_LIST_CELL ValueListCell;
993 PKEY_CELL KeyCell;
994
995 KeyCell = CmiGetCell (Hive, KeyCellOffset, NULL);
996 if (KeyCell == NULL)
997 {
998 DPRINT1 ("CmiGetBlock() failed\n");
999 return FALSE;
1000 }
1001
1002 ValueListCell = CmiGetCell (Hive, KeyCell->ValueListOffset, NULL);
1003 if (ValueListCell == NULL)
1004 {
1005 DPRINT1 ("CmiGetBlock() failed\n");
1006 return FALSE;
1007 }
1008
1009 ValueListCell->ValueOffset[KeyCell->NumberOfValues] = ValueCellOffset;
1010 KeyCell->NumberOfValues++;
1011
1012 return TRUE;
1013 }
1014
1015
1016 static BOOL
1017 CmiExportValue (PREGISTRY_HIVE Hive,
1018 BLOCK_OFFSET KeyCellOffset,
1019 HKEY Key,
1020 PVALUE Value)
1021 {
1022 BLOCK_OFFSET ValueCellOffset;
1023 BLOCK_OFFSET DataCellOffset;
1024 PVALUE_CELL ValueCell;
1025 PDATA_CELL DataCell;
1026 ULONG SrcDataSize;
1027 ULONG DstDataSize;
1028 ULONG DataType;
1029 PCHAR Data;
1030 BOOL Expand = FALSE;
1031
1032 DPRINT ("CmiExportValue('%s') called\n", (Value == NULL) ? "<default>" : (PCHAR)Value->Name);
1033 DPRINT ("DataSize %lu\n", (Value == NULL) ? Key->DataSize : Value->DataSize);
1034
1035 /* Allocate value cell */
1036 if (!CmiAllocateValueCell(Hive, &ValueCell, &ValueCellOffset, (Value == NULL) ? NULL : Value->Name))
1037 {
1038 return FALSE;
1039 }
1040
1041 if (!CmiAddValueToKeyValueList(Hive, KeyCellOffset, ValueCellOffset))
1042 {
1043 return FALSE;
1044 }
1045
1046 if (Value == NULL)
1047 {
1048 DataType = Key->DataType;
1049 SrcDataSize = Key->DataSize;
1050 Data = Key->Data;
1051 }
1052 else
1053 {
1054 DataType = Value->DataType;
1055 SrcDataSize = Value->DataSize;
1056 Data = Value->Data;
1057 }
1058
1059 DstDataSize = SrcDataSize;
1060 if (DataType == REG_SZ ||
1061 DataType == REG_EXPAND_SZ ||
1062 DataType == REG_MULTI_SZ)
1063 {
1064 DstDataSize *= sizeof(WCHAR);
1065 Expand = TRUE;
1066 }
1067
1068 if ((DstDataSize & REG_DATA_SIZE_MASK) <= sizeof(BLOCK_OFFSET))
1069 {
1070 ValueCell->DataSize = DstDataSize | REG_DATA_IN_OFFSET;
1071 ValueCell->DataType = DataType;
1072 if (Expand)
1073 {
1074 memexpand ((PWCHAR)&ValueCell->DataOffset,
1075 (PCHAR)&Data,
1076 SrcDataSize);
1077 }
1078 else
1079 {
1080 memcpy (&ValueCell->DataOffset,
1081 &Data,
1082 SrcDataSize);
1083 }
1084 }
1085 else
1086 {
1087 /* Allocate data cell */
1088 if (!CmiAllocateCell (Hive,
1089 sizeof(CELL_HEADER) + DstDataSize,
1090 (PVOID *)&DataCell,
1091 &DataCellOffset))
1092 {
1093 return FALSE;
1094 }
1095
1096 ValueCell->DataOffset = DataCellOffset;
1097 ValueCell->DataSize = DstDataSize & REG_DATA_SIZE_MASK;
1098 ValueCell->DataType = DataType;
1099
1100 if (Expand)
1101 {
1102 if (SrcDataSize <= sizeof(BLOCK_OFFSET))
1103 {
1104 memexpand ((PWCHAR)DataCell->Data,
1105 (PCHAR)&Data,
1106 SrcDataSize);
1107 }
1108 else
1109 {
1110 memexpand ((PWCHAR)DataCell->Data,
1111 Data,
1112 SrcDataSize);
1113 }
1114 }
1115 else
1116 {
1117 memcpy (DataCell->Data,
1118 Data,
1119 SrcDataSize);
1120 }
1121 }
1122
1123 return TRUE;
1124 }
1125
1126
1127 static BOOL
1128 CmiExportSubKey (PREGISTRY_HIVE Hive,
1129 BLOCK_OFFSET ParentKeyOffset,
1130 HKEY ParentKey,
1131 HKEY Key)
1132 {
1133 BLOCK_OFFSET NKBOffset;
1134 PKEY_CELL NewKeyCell;
1135 ULONG KeyCellSize;
1136 USHORT SubKeyCount;
1137 ULONG ValueCount;
1138 PLIST_ENTRY Entry;
1139 HKEY SubKey;
1140 PVALUE Value;
1141
1142 DPRINT ("CmiExportSubKey('%s') called\n", Key->Name);
1143
1144 /* Don't export links */
1145 if (Key->DataType == REG_LINK)
1146 return TRUE;
1147
1148 /* Allocate key cell */
1149 KeyCellSize = sizeof(KEY_CELL) + Key->NameSize - 1;
1150 if (!CmiAllocateCell (Hive, KeyCellSize, (PVOID)&NewKeyCell, &NKBOffset))
1151 {
1152 DPRINT1 ("CmiAllocateBlock() failed\n");
1153 return FALSE;
1154 }
1155
1156 /* Initialize key cell */
1157 NewKeyCell->Id = REG_KEY_CELL_ID;
1158 NewKeyCell->Type = REG_KEY_CELL_TYPE;
1159 NewKeyCell->LastWriteTime = 0;
1160 NewKeyCell->ParentKeyOffset = ParentKeyOffset;
1161 NewKeyCell->NumberOfSubKeys = 0;
1162 NewKeyCell->HashTableOffset = -1;
1163 NewKeyCell->NumberOfValues = 0;
1164 NewKeyCell->ValueListOffset = -1;
1165 NewKeyCell->SecurityKeyOffset = -1;
1166 NewKeyCell->NameSize = Key->NameSize - 1;
1167 NewKeyCell->ClassNameOffset = -1;
1168 memcpy (NewKeyCell->Name,
1169 Key->Name,
1170 Key->NameSize - 1);
1171
1172 /* Add key cell to the parent key's hash table */
1173 if (!CmiAddKeyToParentHashTable (Hive,
1174 ParentKeyOffset,
1175 NewKeyCell,
1176 NKBOffset))
1177 {
1178 DPRINT1 ("CmiAddKeyToParentHashTable() failed\n");
1179 return FALSE;
1180 }
1181
1182 ValueCount = RegGetValueCount (Key);
1183 DPRINT ("ValueCount: %lu\n", ValueCount);
1184 if (ValueCount > 0)
1185 {
1186 /* Allocate value list cell */
1187 CmiAllocateValueListCell (Hive,
1188 &NewKeyCell->ValueListOffset,
1189 ValueCount);
1190
1191 if (Key->DataSize != 0)
1192 {
1193 if (!CmiExportValue (Hive, NKBOffset, Key, NULL))
1194 return FALSE;
1195 }
1196
1197 /* Enumerate values */
1198 Entry = Key->ValueList.Flink;
1199 while (Entry != &Key->ValueList)
1200 {
1201 Value = CONTAINING_RECORD(Entry,
1202 VALUE,
1203 ValueList);
1204
1205 if (!CmiExportValue (Hive, NKBOffset, Key, Value))
1206 return FALSE;
1207
1208 Entry = Entry->Flink;
1209 }
1210 }
1211
1212 SubKeyCount = RegGetSubKeyCount (Key);
1213 DPRINT ("SubKeyCount: %lu\n", SubKeyCount);
1214 if (SubKeyCount > 0)
1215 {
1216 /* Allocate hash table cell */
1217 CmiAllocateHashTableCell (Hive,
1218 &NewKeyCell->HashTableOffset,
1219 SubKeyCount);
1220
1221 /* Enumerate subkeys */
1222 Entry = Key->SubKeyList.Flink;
1223 while (Entry != &Key->SubKeyList)
1224 {
1225 SubKey = CONTAINING_RECORD(Entry,
1226 KEY,
1227 KeyList);
1228
1229 if (!CmiExportSubKey (Hive, NKBOffset, Key, SubKey))
1230 return FALSE;
1231
1232 Entry = Entry->Flink;
1233 }
1234 }
1235
1236 return TRUE;
1237 }
1238
1239
1240 static VOID
1241 CmiCalcHiveChecksum (PREGISTRY_HIVE Hive)
1242 {
1243 PULONG Buffer;
1244 ULONG Sum;
1245 ULONG i;
1246
1247 Buffer = (PULONG)Hive->HiveHeader;
1248 Sum = 0;
1249 for (i = 0; i < 127; i++)
1250 Sum += Buffer[i];
1251
1252 Hive->HiveHeader->Checksum = Sum;
1253 }
1254
1255
1256 BOOL
1257 CmiExportHive (PREGISTRY_HIVE Hive,
1258 PCHAR KeyName)
1259 {
1260 PKEY_CELL KeyCell;
1261 HKEY Key;
1262 USHORT SubKeyCount;
1263 ULONG ValueCount;
1264 PLIST_ENTRY Entry;
1265 HKEY SubKey;
1266 PVALUE Value;
1267
1268 DPRINT ("CmiExportHive(%p, '%s') called\n", Hive, KeyName);
1269
1270 if (RegOpenKey (NULL, KeyName, &Key) != ERROR_SUCCESS)
1271 {
1272 DPRINT1 ("RegOpenKey() failed\n");
1273 return FALSE;
1274 }
1275
1276 DPRINT ("Name: %s\n", KeyName);
1277
1278 KeyCell = CmiGetCell (Hive,
1279 Hive->HiveHeader->RootKeyOffset,
1280 NULL);
1281 if (KeyCell == NULL)
1282 {
1283 DPRINT1 ("CmiGetCell() failed\n");
1284 return FALSE;
1285 }
1286
1287 ValueCount = RegGetValueCount (Key);
1288 DPRINT ("ValueCount: %lu\n", ValueCount);
1289 if (ValueCount > 0)
1290 {
1291 /* Allocate value list cell */
1292 CmiAllocateValueListCell (Hive,
1293 &KeyCell->ValueListOffset,
1294 ValueCount);
1295
1296 if (Key->DataSize != 0)
1297 {
1298 if (!CmiExportValue (Hive, Hive->HiveHeader->RootKeyOffset, Key, NULL))
1299 return FALSE;
1300 }
1301
1302 /* Enumerate values */
1303 Entry = Key->ValueList.Flink;
1304 while (Entry != &Key->ValueList)
1305 {
1306 Value = CONTAINING_RECORD(Entry,
1307 VALUE,
1308 ValueList);
1309
1310 if (!CmiExportValue (Hive, Hive->HiveHeader->RootKeyOffset, Key, Value))
1311 return FALSE;
1312
1313 Entry = Entry->Flink;
1314 }
1315 }
1316
1317 SubKeyCount = RegGetSubKeyCount (Key);
1318 DPRINT ("SubKeyCount: %lu\n", SubKeyCount);
1319 if (SubKeyCount > 0)
1320 {
1321 /* Allocate hash table cell */
1322 CmiAllocateHashTableCell (Hive,
1323 &KeyCell->HashTableOffset,
1324 SubKeyCount);
1325
1326 /* Enumerate subkeys */
1327 Entry = Key->SubKeyList.Flink;
1328 while (Entry != &Key->SubKeyList)
1329 {
1330 SubKey = CONTAINING_RECORD(Entry,
1331 KEY,
1332 KeyList);
1333
1334 if (!CmiExportSubKey (Hive, Hive->HiveHeader->RootKeyOffset, Key, SubKey))
1335 return FALSE;
1336
1337 Entry = Entry->Flink;
1338 }
1339 }
1340
1341 CmiCalcHiveChecksum (Hive);
1342
1343 return TRUE;
1344 }
1345
1346
1347 static BOOL
1348 CmiWriteHive(PREGISTRY_HIVE Hive,
1349 PCHAR FileName)
1350 {
1351 PHBIN Bin;
1352 FILE *File;
1353 ULONG i;
1354
1355 #if 0
1356 /* Check for existing hive file */
1357 File = fopen (FileName, "rb");
1358 if (File != NULL)
1359 {
1360 printf (" File already exists\n");
1361 fclose (File);
1362 return TRUE;
1363 }
1364 #endif
1365
1366 /* Create new hive file */
1367 File = fopen (FileName, "w+b");
1368 if (File == NULL)
1369 {
1370 printf(" Error creating/opening file\n");
1371 return FALSE;
1372 }
1373
1374 fseek (File, 0, SEEK_SET);
1375
1376 /* Calculate header checksum */
1377 CmiCalcHiveChecksum (Hive);
1378
1379 /* Write hive header */
1380 fwrite (Hive->HiveHeader, REG_BLOCK_SIZE, 1, File);
1381
1382 Bin = NULL;
1383 for (i = 0; i < Hive->BlockListSize; i++)
1384 {
1385 if (Hive->BlockList[i] != Bin)
1386 {
1387 Bin = Hive->BlockList[i];
1388
1389 DPRINT ("Bin[%lu]: Offset 0x%lx Size 0x%lx\n",
1390 i, Bin->BinOffset, Bin->BinSize);
1391
1392 fwrite (Bin, Bin->BinSize, 1, File);
1393 }
1394 }
1395
1396 fclose (File);
1397
1398 return TRUE;
1399 }
1400
1401
1402 BOOL
1403 ExportBinaryHive (PCHAR FileName,
1404 PCHAR KeyName)
1405 {
1406 PREGISTRY_HIVE Hive;
1407
1408 printf (" Creating binary hive: %s\n", FileName);
1409
1410 Hive = CmiCreateRegistryHive (KeyName);
1411 if (Hive == NULL)
1412 return FALSE;
1413
1414 if (!CmiExportHive (Hive, KeyName))
1415 {
1416 CmiDestroyRegistryHive (Hive);
1417 return FALSE;
1418 }
1419
1420 if (!CmiWriteHive (Hive, FileName))
1421 {
1422 CmiDestroyRegistryHive (Hive);
1423 return FALSE;
1424 }
1425
1426 CmiDestroyRegistryHive (Hive);
1427
1428 return TRUE;
1429 }
1430
1431 /* EOF */