gitweb.ps.run Git - ziggit/blob - main.zig

   1 const std = @import("std");
   2
   3 const GitObject = struct {
   4     type: u3,
   5     data: []const u8,
   6 };
   7
   8 fn getSize(buffer: []const u8, ignoreTypeBits: bool) struct { size: u64, bytelen: u64 } {
   9     var size: u64 = 0;
  10     var counter: u6 = 0;
  11     while (true) {
  12         if (counter == 0) {
  13             if (ignoreTypeBits) {
  14                 const bits: u4 = @truncate(buffer[counter]);
  15                 size = bits;
  16             } else {
  17                 const bits: u7 = @truncate(buffer[counter]);
  18                 size = bits;
  19             }
  20         } else {
  21             if (ignoreTypeBits) {
  22                 const bits: u7 = @truncate(buffer[counter]);
  23                 size += @as(u64, bits) << (7 * (counter - 1) + 4);
  24             } else {
  25                 const bits: u7 = @truncate(buffer[counter]);
  26                 size += @as(u64, bits) << (7 * (counter));
  27             }
  28         }
  29
  30         if (buffer[counter] & 0b10000000 == 0) {
  31             break;
  32         }
  33
  34         counter += 1;
  35     }
  36
  37     const nBytes = counter + 1;
  38
  39     return .{
  40         .size = size,
  41         .bytelen = nBytes,
  42     };
  43 }
  44
  45 fn getOffset(buffer: []const u8) struct { offset: u64, bytelen: u64 } {
  46     var offset: u64 = 0;
  47     var counter: u4 = 0;
  48     while (true) {
  49         const bits: u7 = @truncate(buffer[counter]);
  50         offset <<= 7;
  51         offset += @as(u64, bits);
  52
  53         if (buffer[counter] & 0b10000000 == 0) {
  54             break;
  55         }
  56
  57         counter += 1;
  58     }
  59
  60     const nBytes = counter + 1;
  61
  62     if (nBytes >= 2) {
  63         for (1..nBytes) |i| {
  64             offset += std.math.pow(u64, 2, 7 * i);
  65         }
  66     }
  67     return .{
  68         .offset = offset,
  69         .bytelen = nBytes,
  70     };
  71 }
  72
  73 fn decompress(alloc: std.mem.Allocator, inBuffer: []const u8, size: usize) ![]u8 {
  74     const outBuffer = try alloc.alloc(u8, size);
  75     errdefer alloc.free(outBuffer);
  76
  77     var inFbs = std.io.fixedBufferStream(inBuffer);
  78     const reader = inFbs.reader();
  79
  80     var outFbs = std.io.fixedBufferStream(outBuffer);
  81     const writer = outFbs.writer();
  82
  83     try std.compress.zlib.decompress(reader, writer);
  84
  85     return outBuffer;
  86 }
  87
  88 fn applyDelta(alloc: std.mem.Allocator, baseData: []const u8, deltaData: []const u8) ![]const u8 {
  89     const baseObjectSize = getSize(deltaData, false);
  90     const resultObjectSize = getSize(deltaData[baseObjectSize.bytelen..deltaData.len], false);
  91     const deltaDataOffset = baseObjectSize.bytelen + resultObjectSize.bytelen;
  92
  93     // std.debug.print("base: {}, result: {}\n", .{ baseObjectSize.size, resultObjectSize.size });
  94
  95     const result = try alloc.alloc(u8, resultObjectSize.size);
  96     var resultCounter: u64 = 0;
  97
  98     var counter: u64 = 0;
  99     while (true) {
 100         const b = deltaData[deltaDataOffset + counter];
 101
 102         if (b & 0b10000000 != 0) {
 103             // if (b == 0b10010000) {
 104             //     counter += 1;
 105             // } else {
 106             var dataOffset: u64 = 0;
 107             var dataSize: u64 = 0;
 108             var bitsSet: u8 = 0;
 109             for (0..4) |i| { // offset bits
 110                 if (b & (@as(u64, 1) << @min(3, i)) != 0) {
 111                     dataOffset += @as(u64, deltaData[deltaDataOffset + counter + 1 + bitsSet]) << @min(3 * 8, i * 8);
 112                     bitsSet += 1;
 113                 }
 114             }
 115             for (4..7) |i| { // size bits
 116                 if (b & (@as(u64, 1) << @min(6, i)) != 0) {
 117                     dataSize += @as(u64, deltaData[deltaDataOffset + counter + 1 + bitsSet]) << @min(6 * 8, (i - 4) * 8);
 118                     bitsSet += 1;
 119                 }
 120             }
 121             counter += bitsSet;
 122
 123             // std.debug.print("copying {} bytes of from {} data[{b:0>8}]: {s}\n", .{ dataSize, dataOffset, b, baseData[dataOffset .. dataOffset + dataSize] });
 124
 125             std.mem.copyForwards(
 126                 u8,
 127                 result[resultCounter..result.len],
 128                 baseData[dataOffset .. dataOffset + dataSize],
 129             );
 130
 131             resultCounter += dataSize;
 132             // }
 133         } else {
 134             const dataSize: u7 = @truncate(b);
 135             // std.debug.print("pasting {} bytes: {s}\n", .{ dataSize, deltaData[deltaDataOffset + counter + 1 .. deltaDataOffset + counter + 1 + dataSize] });
 136             std.mem.copyForwards(
 137                 u8,
 138                 result[resultCounter..result.len],
 139                 deltaData[deltaDataOffset + counter + 1 .. deltaDataOffset + counter + 1 + dataSize],
 140             );
 141             resultCounter += dataSize;
 142             counter += dataSize;
 143         }
 144
 145         counter += 1;
 146         if (deltaDataOffset + counter >= deltaData.len)
 147             break;
 148     }
 149
 150     alloc.free(deltaData);
 151     return result;
 152 }
 153
 154 fn parseObject(alloc: std.mem.Allocator, objectType: u3, objectData: []const u8) !git.Object {
 155     if (objectType == 3) {
 156         return .{
 157             .data = objectData,
 158             .blob = .{
 159                 .data = objectData[0..@min(objectData.len, 1000)],
 160             },
 161         };
 162     } else if (objectType == 2) {
 163         var treeEntries = git.Tree.init(alloc);
 164
 165         var counter: u64 = 0;
 166         while (counter < objectData.len) {
 167             const modeLen = std.mem.indexOfScalar(u8, objectData[counter..objectData.len], ' ') orelse break;
 168             const mode = objectData[counter .. counter + modeLen];
 169             counter += modeLen + 1;
 170
 171             var nameLen: u64 = 0;
 172             while (counter + nameLen < objectData.len and objectData[counter + nameLen] != 0) {
 173                 nameLen += 1;
 174             }
 175             const name = objectData[counter .. counter + nameLen];
 176             counter += nameLen + 1;
 177
 178             if (counter + 20 <= objectData.len) {
 179                 const hash: u160 = std.mem.readVarInt(u160, objectData[counter .. counter + 20], .big);
 180                 counter += 20;
 181
 182                 treeEntries.append(.{
 183                     .mode = alloc.dupe(u8, mode),
 184                     .name = alloc.dupe(u8, name),
 185                     .hash = hash,
 186                 });
 187             }
 188         }
 189         return .{
 190             .tree = treeEntries,
 191         };
 192     } else {
 193         std.debug.print("type: {}\n{s}\n", .{ objectType, objectData });
 194     }
 195 }
 196
 197 const PackFile = struct {
 198     alloc: std.mem.Allocator,
 199     version: i32,
 200     objectNames: std.ArrayList(u160),
 201     objectOffsets: std.ArrayList(u32),
 202     packBuffer: []const u8,
 203     idxBuffer: []const u8,
 204     // TODO:
 205     // - decompress
 206     // - applyDelta
 207
 208     pub fn init(alloc: std.mem.Allocator, packBuffer: []const u8, idxBuffer: []const u8) !PackFile {
 209         var result: PackFile = undefined;
 210         result.alloc = alloc;
 211         result.packBuffer = packBuffer;
 212         result.idxBuffer = idxBuffer;
 213
 214         result.version = std.mem.readInt(i32, idxBuffer[4..8], .big);
 215
 216         // N-th entry of this table records the number of objects in the corresponding pack,
 217         // the first byte of whose object name is less than or equal to N.
 218         var fanoutTable: [256]u32 = undefined;
 219         result.objectNames = std.ArrayList(u160).init(alloc);
 220         // result.crc32s = std.ArrayList(u32).init(alloc);
 221         result.objectOffsets = std.ArrayList(u32).init(alloc);
 222
 223         for (0..256) |i| {
 224             fanoutTable[i] = std.mem.readVarInt(u32, idxBuffer[8 + i * 4 .. 8 + i * 4 + 4], .big);
 225             const numObjects = if (i > 0) fanoutTable[i] - fanoutTable[i - 1] else fanoutTable[i];
 226             // print("{} objects starting with {x:02}\n", .{ numObjects, i });
 227
 228             for (0..numObjects) |j| {
 229                 const nameOffset = 4 + 4 + 4 * 256 + (j + if (i > 0) fanoutTable[i - 1] else 0) * 20;
 230                 const objectName = idxBuffer[nameOffset .. nameOffset + 20];
 231                 const objectNameInt = std.mem.readVarInt(u160, objectName, .big);
 232                 // print("object name: {x}\n", .{objectNameInt});
 233                 try result.objectNames.append(objectNameInt);
 234             }
 235         }
 236
 237         for (0..result.objectNames.items.len) |i| {
 238             const offsetOffset = 4 + 4 + 4 * 256 + result.objectNames.items.len * (20 + 4) + i * 4;
 239             const offsetInt = std.mem.readVarInt(u32, idxBuffer[offsetOffset .. offsetOffset + 4], .big);
 240
 241             try result.objectOffsets.append(offsetInt);
 242         }
 243
 244         return result;
 245     }
 246
 247     pub fn deinit(self: @This()) void {
 248         self.objectNames.deinit();
 249         self.objectOffsets.deinit();
 250     }
 251
 252     pub fn findObjectOffset(self: @This(), name: u160) ?usize {
 253         for (0..self.objectNames.items.len) |i| {
 254             if (self.objectNames.items[i] == name)
 255                 return self.objectOffsets.items[i];
 256         }
 257         return null;
 258     }
 259
 260     pub fn getObject(self: @This(), alloc: std.mem.Allocator, index: u64) !git.Object {
 261         var objectType: u3 = @truncate(self.packBuffer[index] >> 4);
 262         const objectSize = getSize(self.packBuffer[index..self.packBuffer.len], true);
 263
 264         // std.debug.print("getting object at index {}. type: {}, size: {}.\n", .{
 265         //     index,
 266         //     objectType,
 267         //     objectSize.size,
 268         // });
 269
 270         var objectData: []const u8 = undefined;
 271
 272         if (objectType == 6) {
 273             const offsetSize = getOffset(
 274                 self.packBuffer[index + objectSize.bytelen .. self.packBuffer.len],
 275             );
 276
 277             const baseIndex = index - offsetSize.offset;
 278
 279             const baseObject = try self.getObject(alloc, baseIndex);
 280             defer self.alloc.free(baseObject.data);
 281
 282             const deltaData = try decompress(
 283                 self.alloc,
 284                 self.packBuffer[index + objectSize.bytelen + offsetSize.bytelen .. self.packBuffer.len],
 285                 objectSize.size,
 286             );
 287             objectData = try applyDelta(self.alloc, baseObject.data, deltaData);
 288             objectType = baseObject.type;
 289         } else if (objectType == 7) {
 290             const baseObjectName = self.packBuffer[index + objectSize.bytelen .. index + objectSize.bytelen + 20];
 291             const baseObjectNameInt = std.mem.readVarInt(u160, baseObjectName, .big);
 292             var baseObjectOffset: ?u64 = null;
 293             for (0..self.objectNames.items.len) |i| {
 294                 if (baseObjectNameInt == self.objectNames.items[i]) {
 295                     baseObjectOffset = i;
 296                     break;
 297                 }
 298             }
 299             if (baseObjectOffset) |offset| {
 300                 const baseObject = try self.getObject(offset);
 301                 defer self.alloc.free(baseObject.data);
 302                 const deltaData = try decompress(
 303                     self.alloc,
 304                     self.packBuffer[index + objectSize.bytelen + 20 .. self.packBuffer.len],
 305                     objectSize.size,
 306                 );
 307                 objectData = try applyDelta(self.alloc, baseObject.data, deltaData);
 308                 objectType = baseObject.type;
 309             } else {
 310                 std.debug.print("object {x} not found\n", .{baseObjectNameInt});
 311             }
 312         } else {
 313             objectData = try decompress(
 314                 self.alloc,
 315                 self.packBuffer[index + objectSize.bytelen .. self.packBuffer.len],
 316                 objectSize.size,
 317             );
 318         }
 319
 320         return try parseObject(alloc, objectType, objectData);
 321     }
 322 };
 323
 324 const git = struct {
 325     const Blob = struct {
 326         data: []u8,
 327     };
 328     const TreeEntry = struct {
 329         mode: []u8,
 330         name: []u8,
 331         hash: u160,
 332     };
 333     const Tree = std.ArrayList(TreeEntry);
 334     const Commit = struct {
 335         author: []u8,
 336         message: []u8,
 337         parent: u160,
 338         Tree: u160,
 339     };
 340     const Object = struct {
 341         usingnamespace union(enum) {
 342             blob: Blob,
 343             tree: Tree,
 344             commit: Commit,
 345         };
 346         data: []const u8,
 347     };
 348     const Repo = struct {
 349         pub fn init(alloc: std.mem.Allocator, path: []const u8) !@This() {
 350             const gitDir = try std.fs.cwd().openDir(path, .{});
 351
 352             var objects = std.AutoHashMap(u160, Object).init(alloc);
 353
 354             var iter = gitDir.iterate();
 355             while (try iter.next()) |dirEntry| {
 356                 if (std.mem.endsWith(u8, dirEntry.name, ".idx")) {
 357                     var packPathBuffer: [128]u8 = undefined;
 358                     const idxPath = try gitDir.realpathAlloc(alloc, dirEntry.name);
 359                     const packPath = try std.fmt.bufPrint(
 360                         &packPathBuffer,
 361                         "{s}.pack",
 362                         .{idxPath[0 .. idxPath.len - 4]},
 363                     );
 364
 365                     const packBuffer = try std.fs.cwd().readFileAlloc(alloc, packPath, 1024 * 1024 * 1024 * 1024);
 366                     const idxBuffer = try std.fs.cwd().readFileAlloc(alloc, idxPath, 1024 * 1024 * 1024 * 1024);
 367                     defer alloc.free(packBuffer);
 368                     defer alloc.free(idxBuffer);
 369
 370                     const pf = try PackFile.init(alloc, packBuffer, idxBuffer);
 371                     defer pf.deinit();
 372
 373                     for (0..pf.objectNames.items.len) |i| {
 374                         try objects.put(
 375                             pf.objectNames.items[i],
 376                             try pf.getObject(alloc, pf.objectOffsets.items[i]),
 377                         );
 378                     }
 379                 }
 380             }
 381             return .{
 382                 .alloc = alloc,
 383                 .objects = objects,
 384             };
 385         }
 386
 387         pub fn deinit(self: *@This()) void {
 388             self.objects.deinit();
 389         }
 390
 391         alloc: std.mem.Allocator,
 392         objects: std.AutoHashMap(u160, Object),
 393     };
 394 };
 395
 396 pub fn main() !void {
 397     // allocator
 398     var allocator = std.heap.GeneralPurposeAllocator(.{}){};
 399     const alloc = allocator.allocator();
 400     defer {
 401         const res = allocator.deinit();
 402         std.debug.print("{}\n", .{res});
 403     }
 404
 405     // open repo
 406     var repo = try git.Repo.init(alloc, "../microwindows/.git/");
 407
 408     // input
 409     const r = std.io.getStdIn().reader();
 410     var inputBuffer = std.mem.zeroes([1024]u8);
 411
 412     // print HEAD
 413     // const head = repo.getHead();
 414     // const headObject = head.getObject();
 415     // std.debug.print("HEAD: {x:0>40}\n", .{headObject.id});
 416
 417     // main loop
 418     while (true) {
 419         // read line
 420         const input = r.readUntilDelimiter(&inputBuffer, '\n') catch continue;
 421
 422         // parse object id
 423         const id = std.fmt.parseInt(u160, input, 16) catch continue;
 424
 425         // print object
 426         if (repo.objects.get(id)) |o| {
 427             switch (o) {
 428                 .Blob => |blob| {
 429                     std.debug.print("blob: {s}\n\n", .{blob.data});
 430                 },
 431                 .Tree => |tree| {
 432                     for (tree.entries) |entry| {
 433                         std.debug.print("{s} {s} {x:0>40}\n", .{ entry.mode, entry.name, entry.hash });
 434                     }
 435                     std.debug.print("\n", .{});
 436                 },
 437                 .Commit => |commit| {
 438                     std.debug.print("commit: {}", .{commit});
 439                 },
 440             }
 441         }
 442     }
 443 }