debug.c: new debug line information format `mrb_debug_line_packed_map`.

It uses BER number compression of delta of instruction positions and line
numbers. BER compression is a variable length number representation.

* `mrb_debug_line_ary`: array of line numbers represented in `uint16_t`.
  `[lineno, lineno, ...]`

* `mrb_debug_line_flat_map`: array of `mrb_irep_debug_info_line`, which
  is `struct {uint32_t pos; uint16_t lineno}`, for each line.

* `mrb_debug_line_packed_map` [new]: sequence of BER compressed 2
  numbers, `pos_delta, lineno_delta`. Deltas are differences from
  previous values (starting `0`). `line_entry_counts` represents total
  length of a packed map string for this type.

5 files changed, 165 insertions, 25 deletions

diff --git a/include/mruby/debug.h b/include/mruby/debug.h
index 2062a9308..2e6898e39 100644
--- a/include/mruby/debug.h
+++ b/include/mruby/debug.h
@@ -16,7 +16,8 @@ MRB_BEGIN_DECL
 
 typedef enum mrb_debug_line_type {
   mrb_debug_line_ary = 0,
-  mrb_debug_line_flat_map = 1
+  mrb_debug_line_flat_map,
+  mrb_debug_line_packed_map
 } mrb_debug_line_type;
 
 typedef struct mrb_irep_debug_info_line {
@@ -31,8 +32,9 @@ typedef struct mrb_irep_debug_info_file {
   mrb_debug_line_type line_type;
   union {
     void *ptr;
-    mrb_irep_debug_info_line *flat_map;
     uint16_t *ary;
+    mrb_irep_debug_info_line *flat_map;
+    char *packed_map;
   } lines;
 } mrb_irep_debug_info_file;
 
diff --git a/src/cdump.c b/src/cdump.c
index 9b7040e58..72b4ad0b3 100644
--- a/src/cdump.c
+++ b/src/cdump.c
@@ -258,9 +258,7 @@ cdump_syms(mrb_state *mrb, const char *name, const char *key, int n, int syms_le
 static int
 simple_debug_info(mrb_irep_debug_info *info)
 {
-  if (!info ||
-       info->flen != 1 ||
-       info->files[0]->line_type != mrb_debug_line_ary) {
+  if (!info || info->flen != 1) {
     return 0;
   }
   return 1;
@@ -276,6 +274,7 @@ cdump_debug(mrb_state *mrb, const char *name, int n, mrb_irep_debug_info *info,
   const char *filename;
   mrb_int file_len;
   int len, i;
+  const char *line_type;
 
   if (!simple_debug_info(info))
     return MRB_DUMP_INVALID_IREP;
@@ -289,19 +288,44 @@ cdump_debug(mrb_state *mrb, const char *name, int n, mrb_irep_debug_info *info,
   mrb_str_cat_cstr(mrb, init_syms_code, filename);
   mrb_str_cat_cstr(mrb, init_syms_code, "\");\n");
 
-  fprintf(fp, "static uint16_t %s_debug_lines_%d[%d] = {", name, n, len);
-  for (i=0; i<len; i++) {
-    if (i%10 == 0) fputs("\n", fp);
-    fprintf(fp, "0x%04x,", info->files[0]->lines.ary[i]);
-  }
-  fputs("};\n", fp);
+  switch (info->files[0]->line_type) {
+  case mrb_debug_line_ary:
+    line_type = "mrb_debug_line_ary";
+    fprintf(fp, "static uint16_t %s_debug_lines_%d[%d] = {", name, n, len);
+    for (i=0; i<len; i++) {
+      if (i%10 == 0) fputs("\n", fp);
+      fprintf(fp, "0x%04x,", info->files[0]->lines.ary[i]);
+    }
+    fputs("};\n", fp);
+    break;
 
+  case mrb_debug_line_flat_map:
+    line_type = "mrb_debug_line_flat_map";
+    fprintf(fp, "static struct mrb_irep_debug_info_line %s_debug_lines_%d[%d] = {", name, n, len);
+    for (i=0; i<len; i++) {
+      mrb_irep_debug_info_line *fmap = &info->files[0]->lines.flat_map[i];
+      fprintf(fp, "\t{.start_pos=0x%04x,.line=%d},\n", fmap->start_pos, fmap->line);
+    }
+    fputs("};\n", fp);
+    break;
+
+  case mrb_debug_line_packed_map:
+    line_type = "mrb_debug_line_packed_map";
+    fprintf(fp, "static char %s_debug_lines_%d[] = \"", name, n);
+    char *pmap = info->files[0]->lines.packed_map;
+    for (i=0; i<len; i++) {
+      fprintf(fp, "\\x%02x", pmap[i]&0xff);
+    }
+    fputs("\";\n", fp);
+    break;
+  }
   fprintf(fp, "static mrb_irep_debug_info_file %s_debug_file_%d = {\n", name, n);
-  fprintf(fp, "%d, %d, %d, mrb_debug_line_ary, {%s_debug_lines_%d}};\n",
-      info->files[0]->start_pos,
-      info->files[0]->filename_sym,
-      info->files[0]->line_entry_count,
-      name,n);
+  fprintf(fp, "%d, %d, %d, %s, {%s_debug_lines_%d}};\n",
+          info->files[0]->start_pos,
+          info->files[0]->filename_sym,
+          info->files[0]->line_entry_count,
+          line_type,
+          name,n);
   fprintf(fp, "static mrb_irep_debug_info_file *%s_debug_file_%d_ = &%s_debug_file_%d;\n", name, n, name, n);
 
   fprintf(fp, "static mrb_irep_debug_info %s_debug_%d = {\n", name, n);
diff --git a/src/debug.c b/src/debug.c
index c03c91cf5..f41140edf 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -1,3 +1,4 @@
+#include <stdint.h>
 #include <string.h>
 #include <mruby.h>
 #include <mruby/irep.h>
@@ -35,19 +36,72 @@ get_file(mrb_irep_debug_info *info, uint32_t pc)
   return *ret;
 }
 
+static size_t
+packed_int_len(uint32_t num)
+{
+  size_t llen = 0;
+
+  do {
+    llen++;
+  } while (num >>= 7);
+  return llen;
+}
+
+static size_t
+packed_int_encode(uint32_t num, char *p, char *pend)
+{
+  size_t llen = 0;
+
+  do {
+    uint8_t byte = num & 0x7f;
+    num >>= 7;
+    if (num != 0) byte |= 0x80;
+    if (p < pend) *p++ = byte;
+    llen++;
+  } while (num != 0);
+
+  return llen;
+}
+
+static uint32_t
+packed_int_decode(char *p, char **newpos)
+{
+  size_t i = 0, shift = 0;
+  uint32_t n = 0;
+
+  do {
+    n |= ((uint32_t)(p[i] & 0x7f)) << shift;
+    i++;
+    shift += 7;
+  } while (shift < sizeof(uint32_t) * 8 && (p[i - 1] & 0x80));
+  if (newpos) *newpos = p + i;
+  return n;
+}
+
 static mrb_debug_line_type
 select_line_type(const uint16_t *lines, size_t lines_len)
 {
   size_t line_count = 0;
-  int prev_line = -1;
+  size_t packed_map_len = 0;
+  uint32_t prev_line = 0;
+  uint32_t prev_pc = 0;
   size_t i;
   for (i = 0; i < lines_len; ++i) {
     if (lines[i] != prev_line) {
+      packed_map_len += packed_int_len(lines[i]-prev_line);
+      prev_line = lines[i];
+      packed_map_len += packed_int_len(i-prev_pc);
+      prev_pc = i;
       ++line_count;
     }
   }
-  return (sizeof(uint16_t) * lines_len) <= (sizeof(mrb_irep_debug_info_line) * line_count)
-      ? mrb_debug_line_ary : mrb_debug_line_flat_map;
+  size_t line_ary_len = sizeof(uint16_t) * lines_len;
+  size_t flat_map_len = sizeof(mrb_irep_debug_info_line) * line_count;
+  if (line_ary_len < flat_map_len && line_ary_len < packed_map_len) {
+    return mrb_debug_line_ary;
+  }
+  if (flat_map_len < packed_map_len) return mrb_debug_line_flat_map;
+  return mrb_debug_line_packed_map;
 }
 
 MRB_API char const*
@@ -102,6 +156,19 @@ mrb_debug_get_line(mrb_state *mrb, const mrb_irep *irep, uint32_t pc)
 
           return ret->line;
         }
+
+        case mrb_debug_line_packed_map: {
+          char *p = f->lines.packed_map;
+          char *pend = p + f->line_entry_count;
+          uint32_t pos = 0, line = 0, line_diff;
+          while (p < pend) {
+            pos += packed_int_decode(p, &p);
+            line_diff = packed_int_decode(p, &p);
+            if (pc < pos) break;
+            line += line_diff;
+          }
+          return line;
+        }
       }
     }
   }
@@ -173,23 +240,55 @@ mrb_debug_info_append_file(mrb_state *mrb, mrb_irep_debug_info *d,
     case mrb_debug_line_flat_map: {
       uint16_t prev_line = 0;
       mrb_irep_debug_info_line m;
-      f->lines.flat_map = (mrb_irep_debug_info_line*)mrb_malloc(mrb, sizeof(mrb_irep_debug_info_line) * 1);
       f->line_entry_count = 0;
       for (i = 0; i < file_pc_count; ++i) {
         if (lines[start_pos + i] == prev_line) { continue; }
+        ++f->line_entry_count;
+        prev_line = lines[start_pos + i];
+      }
+      f->lines.flat_map = (mrb_irep_debug_info_line*)mrb_malloc(mrb, sizeof(mrb_irep_debug_info_line) * f->line_entry_count);
+      prev_line = 0;
+      for (i = 0; i < file_pc_count; ++i) {
+        if (lines[start_pos + i] == prev_line) { continue; }
 
-        f->lines.flat_map = (mrb_irep_debug_info_line*)mrb_realloc(
-            mrb, f->lines.flat_map,
-            sizeof(mrb_irep_debug_info_line) * (f->line_entry_count + 1));
         m.start_pos = start_pos + i;
         m.line = lines[start_pos + i];
         f->lines.flat_map[f->line_entry_count] = m;
 
         /* update */
-        ++f->line_entry_count;
         prev_line = lines[start_pos + i];
       }
-    } break;
+      break;
+    }
+
+    case mrb_debug_line_packed_map: {
+      uint32_t prev_line = 0;
+      uint32_t prev_pc = 0;
+      size_t packed_size = 0;
+      char *p, *pend;
+
+      for (i = 0; i < file_pc_count; ++i) {
+        if (lines[start_pos + i] == prev_line) { continue; }
+
+        packed_size += packed_int_len(start_pos+i-prev_pc);
+        prev_pc = start_pos+i;
+        packed_size += packed_int_len(lines[start_pos+i]-prev_line);
+        prev_line = lines[start_pos + i];
+      }
+      p = f->lines.packed_map = (char*)mrb_malloc(mrb, packed_size);
+      pend = p + packed_size;
+      prev_line = 0; prev_pc = 0;
+      for (i = 0; i < file_pc_count; ++i) {
+        if (lines[start_pos + i] == prev_line) { continue; }
+        p += packed_int_encode(start_pos+i-prev_pc, p, pend);
+        prev_pc = start_pos + i;
+        p += packed_int_encode(lines[start_pos + i]-prev_line, p, pend);
+        prev_line = lines[start_pos + i];
+        /* update */
+      }
+      f->line_entry_count = (uint32_t)packed_size;
+      break;
+    }
 
     default: mrb_assert(0); break;
   }
diff --git a/src/dump.c b/src/dump.c
index 0b4200795..628c3dbc4 100644
--- a/src/dump.c
+++ b/src/dump.c
@@ -413,6 +413,10 @@ get_debug_record_size(mrb_state *mrb, const mrb_irep *irep)
         ret += (sizeof(uint32_t) + sizeof(uint16_t)) * (size_t)(file->line_entry_count);
         break;
 
+      case mrb_debug_line_packed_map:
+        ret += (size_t)(file->line_entry_count);
+        break;
+
       default: mrb_assert(0); break;
     }
   }
@@ -507,6 +511,11 @@ write_debug_record_1(mrb_state *mrb, const mrb_irep *irep, uint8_t *bin, mrb_sym
         }
       } break;
 
+      case mrb_debug_line_packed_map: {
+        memcpy(cur, file->lines.packed_map, file->line_entry_count);
+        cur += file->line_entry_count;
+      } break;
+
       default: mrb_assert(0); break;
     }
   }
diff --git a/src/load.c b/src/load.c
index 2e637aa19..d7f01347c 100644
--- a/src/load.c
+++ b/src/load.c
@@ -362,6 +362,12 @@ read_debug_record(mrb_state *mrb, const uint8_t *start, mrb_irep* irep, size_t *
         }
       } break;
 
+      case mrb_debug_line_packed_map: {
+        file->lines.packed_map = (char*)mrb_calloc(mrb, 1, (size_t)file->line_entry_count);
+        memcpy(file->lines.packed_map, bin, file->line_entry_count);
+        bin += file->line_entry_count;
+      } break;
+
       default: return MRB_DUMP_GENERAL_FAILURE;
     }
   }