Documentation of br_ips and ips_patch

2 files changed, 189 insertions, 66 deletions

diff --git a/tools/br_ips/br_ips.c b/tools/br_ips/br_ips.c
index 5426e4e26..9b84973e1 100644
--- a/tools/br_ips/br_ips.c
+++ b/tools/br_ips/br_ips.c
@@ -31,12 +31,24 @@ typedef int ssize_t;
 static const char SPLASH[] = "IPS patch creator for undisassembled data\n"
                              "Created by PikalaxALT on 23 June 2019 All Rights Reserved\n";
 
-struct Baserom {
+static const char HELP[] = "br_ips\n"
+                           "This utility is meant to be run with no arguments in the project root of a PRET AGB disassembly.\n"
+                           "baserom.gba and ld_script.txt are required files which must be present in the project root.\n"
+                           "ld_script.txt is a GNU linker script. For more details, see\n"
+                           "https://ftp.gnu.org/old-gnu/Manuals/ld-2.9.1/html_chapter/ld_3.html#SEC6.\n"
+                           "All ELF targets in the linker script with Makefile rules \"%.o: %.s\" must have their sources present\n"
+                           "at the indicated paths relative to the project root.\n"
+                           "\n"
+                           "Options:\n"
+                           "    -h - show this message and exit\n";
+
+struct Hunk {
     uint32_t offset;
     size_t size;
 };
 
 static ssize_t getline(char ** lineptr, size_t * n, FILE * stream) {
+    // Static implementation of GNU getline
     ssize_t i = 0;
     int c;
     size_t size = *n;
@@ -62,17 +74,20 @@ static ssize_t getline(char ** lineptr, size_t * n, FILE * stream) {
     return i;
 }
 
-static void getIncbinsFromFile(struct Baserom ** incbins, size_t * num, size_t * maxnum, const char * fname, char ** strbuf, size_t * buffersize) {
+static void getIncbinsFromFile(struct Hunk ** hunks, size_t * num, size_t * maxnum, const char * fname, char ** strbuf, size_t * buffersize) {
+    // Recursively find incbinned segments and encode them as hunks.
     FILE * file = fopen(fname, "r");
     if (file == NULL) FATAL_ERROR("unable to open file \"%s\" for reading\n", fname);
-    struct Baserom * data = *incbins;
-    size_t nincbins = *num;
-    size_t maxnincbins = *maxnum;
-    int line_n = 0;
+    struct Hunk * data = *hunks;
+    size_t nhunks = *num;
+    size_t maxnhunks = *maxnum;
+    int line_n = 0; // for error prints
     while (getline(strbuf, buffersize, file) > 0) {
         line_n++;
+        // Replace the newline character with NUL
         char * nl_p = strchr(*strbuf, '\n');
         if (nl_p != NULL) *nl_p = 0;
+        // If another file is included by this one, recurse into it.
         char * include = strstr(*strbuf, ".include");
         if (include != NULL) {
             char incfname[128];
@@ -83,165 +98,251 @@ static void getIncbinsFromFile(struct Baserom ** incbins, size_t * num, size_t *
             if (endq_p == NULL) FATAL_ERROR("%s:%d: malformed include\n", fname, line_n);
             *endq_p = 0;
             strcpy(incfname, include);
-            getIncbinsFromFile(&data, &nincbins, &maxnincbins, incfname, strbuf, buffersize);
+            getIncbinsFromFile(&data, &nhunks, &maxnhunks, incfname, strbuf, buffersize);
             continue;
         }
+        // Check for a .incbin "baserom.gba" directive
         char * line = strstr(*strbuf, ".incbin");
         if (line == NULL) continue;
         line = strstr(line + sizeof(".incbin"), "\"baserom.gba\",");
         if (line == NULL) continue;
         line += sizeof("\"baserom.gba\",") - 1;
         uint32_t incbinOffset;
+        // Enforce the structure .incbin "baserom.gba", offset, size
+        // Data cannot be located at offset 0, as that is the entry
+        // point (ARM code).
         do {
             if (*line == 0) FATAL_ERROR("%s:%d: malformed incbin\n", fname, line_n);
             incbinOffset = strtoul(line, &line, 0);
             line++;
         } while (incbinOffset == 0);
-        ssize_t incbinSize;
+        size_t incbinSize;
         do {
             if (*line == 0) FATAL_ERROR("%s:%d: malformed incbin\n", fname, line_n);
             incbinSize = strtoul(line, &line, 0);
             line++;
         } while (incbinSize == 0);
+        // Offset must fit in three bytes
         if (incbinOffset >= 0x01000000) FATAL_ERROR("%s:%d: offset exceeds encodable limit\n", fname, line_n);
+        // Avoid confusion with the end sentinel
         if (incbinOffset == 0x454F46) { // "EOF"
             incbinOffset--;
             incbinSize++;
         }
-        if (incbinOffset + incbinSize >= 0xFFFFFF + 0xFFFF) FATAL_ERROR("%s:%d: size exceeds encodable limit\n", fname, line_n);
+        // Cannot read past a certain point due to format restrictions
+        if (incbinOffset + incbinSize > 0xFFFFFF + 0xFFFF) FATAL_ERROR("%s:%d: size exceeds encodable limit\n", fname, line_n);
+        // Break up the incbin into hunks of maximum size 0xFFFF
         do {
             size_t trueSize = incbinSize <= 0xFFFF ? incbinSize : 0xFFFF;
-            if (nincbins >= maxnincbins) {
-                maxnincbins <<= 1;
-                data = realloc(data, maxnincbins * sizeof(struct Baserom));
-                if (data == NULL) FATAL_ERROR("unable to reallocate incbins buffer\n");
+            if (nhunks >= maxnhunks) {
+                maxnhunks <<= 1;
+                data = realloc(data, maxnhunks * sizeof(struct Hunk));
+                if (data == NULL) FATAL_ERROR("unable to reallocate hunks buffer\n");
             }
-            data[nincbins].offset = incbinOffset;
-            data[nincbins].size = trueSize;
+            data[nhunks].offset = incbinOffset;
+            data[nhunks].size = trueSize;
             incbinOffset += trueSize;
             incbinSize -= trueSize;
             if (incbinOffset == 0x454F46) {
                 incbinOffset--;
-                data[nincbins].size--;
+                data[nhunks].size--;
                 incbinSize++;
             }
-            nincbins++;
+            nhunks++;
         } while (incbinSize > 0);
     }
+    // Error check
     if (!feof(file)) FATAL_ERROR("getline\n");
     fclose(file);
-    *incbins = data;
-    *num = nincbins;
-    *maxnum = maxnincbins;
+    *hunks = data;
+    *num = nhunks;
+    *maxnum = maxnhunks;
 }
 
-static struct Baserom * getAllIncbins(FILE * ld_script, size_t * num_p) {
+static struct Hunk * getAllIncbins(FILE * ld_script, size_t * num_p) {
+    // Parse the ld script.
+    // Strict adherence to syntax is expected.
     char * line = NULL;
     size_t linesiz = 0;
     char fname_buf[128];
     size_t maxnum = 256;
     size_t num = 0;
-    struct Baserom * incbins = malloc(256 * sizeof(struct Baserom));
-    if (incbins == NULL) FATAL_ERROR("failed to allocate incbins buffer\n");
+    // Allocate the hunks array.
+    struct Hunk * hunks = malloc(256 * sizeof(struct Hunk));
+    if (hunks == NULL) FATAL_ERROR("failed to allocate hunks buffer\n");
     while (getline(&line, &linesiz, ld_script) > 0) {
         char * endptr;
+        // We only expect hunks in rodata, script_data, and gfx_data sections.
         if ((endptr = strstr(line, ".o(.rodata);")) == NULL
          && (endptr = strstr(line, ".o(script_data);")) == NULL
          && (endptr = strstr(line, ".o(gfx_data);")) == NULL) continue;
         char * startptr = line;
+        // Skip whitespace.
         while (isspace(*startptr)) startptr++;
-        if (strstr(startptr, ".a:") != NULL) continue; // no incbins in libs
-        if (strstr(startptr, "src/") == startptr) continue; // no incbins in src/
+        if (strstr(startptr, ".a:") != NULL) continue; // no hunks in libs
+        if (strstr(startptr, "src/") == startptr) continue; // no hunks in src/
+        // Replace the extension with .s and truncate the string
         endptr[1] = 's';
         endptr[2] = 0;
+        // We're reusing the already-allocated string buffer, so
+        // copy the filename to the stack for use in error prints.
         strcpy(fname_buf, startptr);
-        getIncbinsFromFile(&incbins, &num, &maxnum, fname_buf, &line, &linesiz);
+        getIncbinsFromFile(&hunks, &num, &maxnum, fname_buf, &line, &linesiz);
     }
+    // Error check
     if (!feof(ld_script)) FATAL_ERROR("getline\n");
     free(line);
     *num_p = num;
-    return incbins;
+    return hunks;
 }
 
 static int cmp_baserom(const void * a, const void * b) {
-    const struct Baserom * aa = (const struct Baserom *)a;
-    const struct Baserom * bb = (const struct Baserom *)b;
+    // Comparison function for sorting Hunk structs.
+    // For more details, please refer to the qsort man pages.
+    // See also the function "collapseIncbins" below.
+    const struct Hunk * aa = (const struct Hunk *)a;
+    const struct Hunk * bb = (const struct Hunk *)b;
     return (aa->offset > bb->offset) - (aa->offset < bb->offset);
 }
 
-static void collapseIncbins(struct Baserom * incbins, size_t * num_p) {
+static void collapseIncbins(struct Hunk * hunks, size_t * num_p) {
+    // This function merges adjacent hunks where possible.
     size_t num = *num_p;
-    qsort(incbins, num, sizeof(struct Baserom), cmp_baserom);
+    // Sort the array by offset increasing.
+    qsort(hunks, num, sizeof(struct Hunk), cmp_baserom);
+    // We stop at num - 1 because we need to be able to look one
+    // entry ahead in the hunks array.
     for (int i = 0; i < num - 1; i++) {
-        while (incbins[i].offset + incbins[i].size == incbins[i + 1].offset) {
-            if (incbins[i].size == 0xFFFF) break;
-            while (incbins[i].size == 0) {
-                for (int j = i; j < num - 1; j++) incbins[j] = incbins[j + 1];
-                num--;
-                if (i == num - 1) break;
+        // Loop until the next hunk is not adjacent to the current.
+        while (hunks[i].offset + hunks[i].size == hunks[i + 1].offset) {
+            // If this hunk cannot be merged with the next, proceed to the next.
+            if (hunks[i].size == 0xFFFF || (hunks[i].size == 0xFFFE && hunks[i + 1].offset == 0x454F45)) break;
+            // If this hunk is empty, remove it.
+            if (hunks[i].size == 0) {
+                int j;
+                // Find the next non-empty hunk
+                for (j = i + 1; j < num; j++) {
+                    if (hunks[j].size != 0) break;
+                }
+                if (j == num) {
+                    // All remaining hunks are empty
+                    num = i;
+                    break;
+                }
+                // Compaction
+                // Use a for loop instead of memcpy to avoid UB from
+                // overlapping buffers.
+                for (int k = 0; k < num - j; k++) hunks[i + k] = hunks[j + k];
+                num -= j - i;
+                if (i >= num - 1) break;
             }
-            if (i == num - 1) break;
-            incbins[i].size += incbins[i + 1].size;
-            if (incbins[i].size > 0xFFFF) {
-                incbins[i + 1].size = incbins[i].size - 0xFFFF;
-                incbins[i].size = 0xFFFF;
-                incbins[i + 1].offset = incbins[i].offset + 0xFFFF;
-                if (incbins[i + 1].offset == 0x454F46) {
-                    incbins[i].size--;
-                    incbins[i + 1].offset--;
-                    incbins[i + 1].size++;
+            else
+            {
+                // Combine this hunk with the next
+                hunks[i].size += hunks[i + 1].size;
+                if (hunks[i].size > 0xFFFF) {
+                    // Split the hunk back up, it's too big to encode.
+                    // Set the earlier hunk to the maximum permitted size,
+                    // and the following hunk to the remainder.
+                    hunks[i + 1].size = hunks[i].size - 0xFFFF;
+                    hunks[i].size = 0xFFFF;
+                    hunks[i + 1].offset = hunks[i].offset + 0xFFFF;
+                    // If this operation would confuse the hunk with the
+                    // EOF sentinel, fix that.
+                    if (hunks[i + 1].offset == 0x454F46) {
+                        hunks[i].size--;
+                        hunks[i + 1].offset--;
+                        hunks[i + 1].size++;
+                    }
+                    break;
+                } else {
+                    // Compaction
+                    // Use a for loop instead of memcpy to avoid UB from
+                    // overlapping buffers.
+                    for (int j = i + 1; j < num - 1; j++) hunks[j] = hunks[j + 1];
+                    num--;
+                    if (i >= num - 1) break;
                 }
-                break;
-            } else {
-                for (int j = i + 1; j < num - 1; j++) incbins[j] = incbins[j + 1];
-                num--;
-                if (i == num - 1) break;
             }
         }
     }
     *num_p = num;
 }
 
-static void writePatch(const char * filename, const struct Baserom * incbins, size_t num, FILE * rom) {
+static void writePatch(const char * filename, const struct Hunk * hunks, size_t num, FILE * rom) {
+    // Create an IPS patch.
+    // The file is headed with a magic code which is "PATCH" in ASCII.
+    // Following that are the "hunks": 3-byte offset, 2-byte size, and
+    // the literal data. The file is ended with "EOF", again in ASCII.
+    // For that reason, an offset of 0x454F46 cannot be encoded directly.
+    // Offset and size are encoded big-endian.
     FILE * file = fopen(filename, "wb");
     if (file == NULL) FATAL_ERROR("unable to open file \"%s\" for writing\n", filename);
+    // Maximum hunk size is 65535 bytes. For convenience, we allocate a
+    // round 65536 (0x10000). This has no effect on memory consumption,
+    // as malloc will round this up anyway.
     char * readbuf = malloc(0x10000);
     if (readbuf == NULL) FATAL_ERROR("failed to allocate write buffer\n");
     fwrite("PATCH", 1, 5, file); // magic
     for (int i = 0; i < num; i++) {
-        uint32_t offset = incbins[i].offset;
+        // Encode the offset
+        uint32_t offset = hunks[i].offset;
         putc(offset >> 16, file);
         putc(offset >>  8, file);
         putc(offset >>  0, file);
-        size_t size = incbins[i].size;
+        // Encode the size
+        size_t size = hunks[i].size;
         putc(size >> 8, file);
         putc(size >> 0, file);
+        // Yank the data straight from the ROM
         if (fseek(rom, offset, SEEK_SET)) FATAL_ERROR("seek\n");
         if (fread(readbuf, 1, size, rom) != size) FATAL_ERROR("read\n");
         if (fwrite(readbuf, 1, size, file) != size) FATAL_ERROR("write\n");
     }
     free(readbuf);
+    // Write the EOF magic
     fwrite("EOF", 1, 3, file);
     fclose(file);
 }
 
-int main() {
+// This script takes no arguments.
+int main(int argc, char ** argv) {
+    // Show a friendly message
     puts(SPLASH);
+    // If requested, show help message
+    if (argc >= 2 && strcmp(argv[1], "-h") == 0) {
+        puts(HELP);
+        return 0;
+    }
+    // This script expects to be in a PRET AGB disassembly project root.
+    // Required files include baserom.gba, ld_script.txt, and all paths
+    // referenced in ld_script.txt relative to the project root.
     FILE * rom = fopen("baserom.gba", "rb");
     if (rom == NULL) FATAL_ERROR("unable to open \"baserom.gba\" for reading\n");
     FILE * ld_script = fopen("ld_script.txt", "r");
     if (ld_script == NULL) FATAL_ERROR("unable to open \"ld_script.txt\" for reading\n");
+    // Find all instances where segments of baserom.gba are incbinned literaly.
     size_t num = 0;
-    struct Baserom * incbins = getAllIncbins(ld_script, &num);
+    struct Hunk * hunks = getAllIncbins(ld_script, &num);
     fclose(ld_script);
     if (num == 0) {
-        puts("No baserom.gba incbins found!\n");
-    } else {        
-        collapseIncbins(incbins, &num);
-        writePatch("baserom.ips", incbins, num, rom);
+        // If this line is printed, the script was unable to find any
+        // `.incbin "baserom.gba"` lines.
+        // If this is incorrect, please contact the developer.
+        puts("No baserom.gba hunks found!\n"
+             "If there are baserom.gba hunks in this project,\n"
+             "please ping PikalaxALT on the pret discord,\n"
+             "channel #gen-3-help.\n");
+    } else {
+        // Merge neighboring hunks to reduce the number of hunks.
+        collapseIncbins(hunks, &num);
+        // Encode the hunks in the IPS patch.
+        writePatch("baserom.ips", hunks, num, rom);
+        // Communicate status to the user.
+        puts("IPS file created at baserom.ips\n");
     }
+    // Clean up and return.
     fclose(rom);
-    free(incbins);
-    puts("IPS file created at baserom.ips\n");
+    free(hunks);
     return 0;
 }
diff --git a/tools/br_ips/ips_patch.c b/tools/br_ips/ips_patch.c
index 03780cf72..506f23ad7 100644
--- a/tools/br_ips/ips_patch.c
+++ b/tools/br_ips/ips_patch.c
@@ -24,18 +24,36 @@ do {                                        \
 static const char SPLASH[] = "Small IPS patch utility\n"
                              "Created by PikalaxALT on 23 June 2019 All Rights Reserved\n";
 
+static const char HELP[] = "ips_patch [-h] ROM PATCH OUT\n"
+                           "\n"
+                           "    ROM - input ROM file\n"
+                           "    PATCH - IPS patch file to apply\n"
+                           "    OUT - path to write patched ROM\n"
+                           "\n"
+                           "Options:\n"
+                           "    -h - show this message and exit\n";
+
 int main(int argc, char ** argv) {
+    // Show a friendly message
     puts(SPLASH);
-    if (argc != 4) FATAL_ERROR("usage: %s ROM PATCH OUT\n", argv[0]);
+    // If requested, show help message
+    if (argc >= 2 && strcmp(argv[1], "-h") == 0) {
+        puts(HELP);
+        return 0;
+    }
+    // Enforce CLI syntax
+    if (argc != 4) FATAL_ERROR("usage: %s [-h] ROM PATCH OUT\n", argv[0]);
     FILE * rom = fopen(argv[1], "rb");
     if (rom == NULL) FATAL_ERROR("failed to open file \"%s\" for reading\n", argv[1]);
     FILE * patch = fopen(argv[2], "rb");
     if (patch == NULL) FATAL_ERROR("failed to open file \"%s\" for reading\n", argv[2]);
     FILE * out = fopen(argv[3], "wb");
     if (patch == NULL) FATAL_ERROR("failed to open file \"%s\" for writing\n", argv[3]);
+    // IPS magic header
     char magic[5];
     if (fread(magic, 1, 5, patch) != 5) FATAL_ERROR("read magic\n");
     if (memcmp(magic, "PATCH", 5) != 0) FATAL_ERROR("malformed IPS patch\n");
+    // Read the ROM into allocated memory.
     fseek(rom, 0, SEEK_END);
     size_t romsize = ftell(rom);
     fseek(rom, 0, SEEK_SET);
@@ -46,16 +64,20 @@ int main(int argc, char ** argv) {
     while (1) {
         uint32_t offset;
         size_t size;
-        
+        // Read each hunk into the buffer, overwriting previous data.
+        // If two or more hunks overlap, the newest one is retained.
+        // A good IPS patch creator will avoid this.
         offset = (unsigned char)getc(patch) << 16;
         offset |= (unsigned char)getc(patch) << 8;
         offset |= (unsigned char)getc(patch);
-        if (offset == 0x454F46) break;
+        if (offset == 0x454F46) break; // end sentinel "EOF"
         size = (unsigned char)getc(patch) << 8;
         size |= (unsigned char)getc(patch);
+        if (offset + size > romsize) FATAL_ERROR("segment extends past end of ROM\n");
         if (fread(buffer + offset, 1, size, patch) != size) FATAL_ERROR("read segment\n");
     }
     fclose(patch);
+    // Write the patched ROM
     fwrite(buffer, 1, romsize, out);
     fclose(out);
     free(buffer);