OK Somebody Explain This Data Structure To Me ... ?

[revilla]

So staring at MEMS3 maps, trying to decipher more tables, one thing that has puzzled me before is the the first table in the map, Table 0.

It's always 9 x 9, with an X axis scaled with typical MAP values and a Y axis scales with typical RPM values. So far so good. But the data in the table always looked just jumbled up numbers with no obvious structure - except there were lots of ascending or descending sequences so it clearly had some structure hidden in it.

Here it is in a VVC map:

Then tonight I sort of realised how to read it, but it makes no sense to me why they would have done this:

So it's an MAP by RPM table with sensible axis values; but if we completely ignore the axes and just read off the numbers in the body cells, it reads off as a sensible table definition. So they have hidden the data that defines a table inside the body of another completely different layout table.

For example here are the body cells from the table above:

Now if these were just consecutive 16-bit numbers in memory I would read them as a table: X Count = 6, Y Count = 8, followed by the 6 X values in ascending order 6000, 8000, 10000, 12000, 14000, 16000 followed by the 8 Y values in ascending order 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000 followed by the 6*8=48 body cells of the table:

​

Now that's a very sensible looking table. It's a smooth surface shape. In fact ...

.. it's a complete copy of the ignition dwell time table, which is dimensioned by battery voltage and RPM, hidden inside the body data of a table dimensioned by MAP and RPM.

So I then took a look at the same table in some other ECUs, and it gets even stranger. This is from an MPI ECU:

Do the same trick. Here are the body cells:

The first 8 values define a 2D table:

Followed by another table:

And another one:

Then finally PART of another one (as much as will fit into the 9x9 body cells):

And each of these tables are copies of others found in the map, e.g.

The last, partial table is again a copy of the ignition dwell time table.

Any ideas what I'm looking at here? Is it just a bug in the map compiler that was never fixed and which caused it to spit out a messed up Table 0, with data blocks taken from the wrong locations and therefore containing copies of other tables? Seems rather odd to me as a programmer that something as obvious as that wasn't noticed and fixed, but the same thing appears in every single MEMS3 map that I've looked at.

On the other hand I can't think of a single sensible reason to hide table definitions, sometimes incomplete, inside other tables!

PS: Actually as I write this I've just looked at the memory addresses of the 4 tables found above and they are contiguous in the map, so it does just look like the 81 16-bit values (162 bytes of data) for Table 0 are just copied starting from the wrong address. How bizarre!

[revilla]

OK so now I've noticed something that makes it seem even more odd ...

The tables I can see hiding inside Table 0 are not copies of other tables ... they actually are the other tables. They overlap in memory.

e.g.

Table 0 is defined in the index as starting at address $13F3D8.
Table 11 is defined in the index as starting at address $13F400 ... which is only 40 bytes later and overlaps with Table 0, in fact it's the first body cell.

So Table 0 appears to be just a set of orphaned table axes without the body data, and the next table definition follows the axis data, where the body data should be.

Looks more and more like a complete cockup to me.

 

[JonT]

Having poked slightly at more recent engine management code, a lot of it has scary amounts of legacy that no-one wants to go near/change - even if doing so would be massively more efficient.

Is table 0 a bunch of offsets/pointers into the other tables?

Cockup or linker script issue entirely possible too.

 

[revilla]

No there's a separate index towards the end of the map that has the offset pointers to all of the other tables. The actual table addresses change between maps for the same firmware, even the order in memory can change, the one thing that remains constant is the position of each table in the index, as this is what the ECU uses to find a given table. So I have used position in the index as the identifier for tables in my software. Table 0 is the table pointed to be entry 0 in the index. It's not even the first table in memory as the physical order of the tables in memory does not correspond to their order in the index, so table 0 is buried somewhere in the middle of the table block.

This diagram explains what I found in the end:

So the tables are generally stacked one after another at increasing memory addresses. Each table has (X & Y) axis definitions followed by the body (Z) data. Table 0 is for some reason always overlapped by the subsequent tables, so all you get is the axis definitions. The next table follows immediately where you would expect the body data for Table 0 to be. It's like that in every MEMS3 I've looked at, MPI and VVC. There are no other tables where this happens.

The axes for Table 0 don't look to be anything special, I was wondering if the first table was somehow designed to be just a header that defined the scales to be used on axes for other tables or something, but don't seem to contain anything that isn't contained within the other MAP x RPM tables.

I suspect it is something legacy or just a plain error that was baked in and never sorted out.

I've just made my software skip any tables it finds like this now as they don't contain useable data.

Thanks for the comments though.

[JonT]

Thanks, that diagram is nice and clear. Definitely seems odd.

[CharlesElliott]

From my recollection of the work I did on the MEMS a long time ago, there were fast areas of memory that had to be used for certain data lookups - although the address space overlaps, perhaps it was where 'fast' memory was accessed?

[revilla]

OK so the mystery is partly solved ...

I've been digging through the assembly language for the code in the ECU and I've found there are two separate table lookup routines, one of which is used exclusively for this odd Table 0 and another which is used for all the others. I've managed to decipher them in detail and worked out what this table is all about and why it is different.

All of the other tables in the map are effectively CONSTANTS. They are programmed in as part of the map and never change. In the map EEPROM they have the X and Y axis data followed immediately by the Z values of the table.

This table is effectively a VARIABLE. Only the axes are defined in the map. The data is located elsewhere, I believe at the moment in RAM, so the ECU is able to modify the contents of the table at runtime.

The standard lookup routine takes a parameter that points to (or gives an offset in the map to the index for) the table to be looked up from; the Table 0 routine takes a further parameter which is the actual address of the Z value data array in memory. So that's why there is no data for this table in the map, it's elsewhere.

The other difference is that all other tables have WORD sized values (2 bytes for each number). Table 0 has WORD sized X and Y axis values as per normal but BYTE size Z values. I've worked through the two routines byte by bytes and looked in detail at the differences and the Table 0 routine is correctly allowing one byte per Z value throughout.I'm guessing it's in RAM and the limited amount of RAM available on the microcontroller has pushed them to use BYTE. It may be persisted to the 93C66 serial EPROM too.

So it is mapping something that changes at runtime, only needs small value or at least values stored at low resolution. 

I'm thinking something like fuelling adaptation? Maybe it will become clearer as I keep unpicking the code.

I can't any way of sensibly pasting code listings up here but the pictures below show the starts of the routines I have found and the comments I've added as I've unpicked them:

This will probably get completely mangled by the content management system but here's the full source of the Table 0 routine for anyone who like staring at such things!

ROM:00115C4E ; =============== S U B R O U T I N E =======================================
ROM:00115C4E
ROM:00115C4E ; Called to look up values in 3D Table 0 only.
ROM:00115C4E ; 
ROM:00115C4E ; Table 0 is a special table:
ROM:00115C4E ; 
ROM:00115C4E ;   The Z values are BYTE sized rather than WORD sized.
ROM:00115C4E ;   The Z values are located at a difference address (poosibly in RAM?).
ROM:00115C4E ; 
ROM:00115C4E ;   On entry:
ROM:00115C4E ; 
ROM:00115C4E ;     Register a5 points to the map = $13c000
ROM:00115C4E ;     Register a1 points to the z array of values.
ROM:00115C4E ;     Register d1 low word holds the offset in the map to the table index entry.
ROM:00115C4E ;     Register d2 low word holds the x axis lookup value.
ROM:00115C4E ;     Register d3 low word holds the y axis lookup value (for a 3D table).
ROM:00115C4E ; 
ROM:00115C4E ;   On exit:
ROM:00115C4E ; 
ROM:00115C4E ;     Register d1 low word holds the looked up or interpolated value.
ROM:00115C4E ;     Register d0 low byte holds $00 on success, or $ff on failure.
ROM:00115C4E ; 
ROM:00115C4E ;       Failure conditions: Either axis has less than 1 value.
ROM:00115C4E
ROM:00115C4E Lookup_Table_0:
ROM:00115C4E  
ROM:00115C4E                 movea.w (a5,d1.w),a0            ; a0 -> map offset to table data
ROM:00115C52                 adda.l  a5,a0                   ; a0 -> address of table data (x_count)
ROM:00115C54                 move.w  (a0)+,d4                ; d4 -> x_count; a0 -> address of y_count
ROM:00115C56                 ble.w   return_error            ; return error code if x_count < 1
ROM:00115C5A                 move.w  (a0)+,d5                ; d5 -> y_count; a0 - > address of x_first
ROM:00115C5C                 ble.w   return_error            ; return error code if y_count < 1
ROM:00115C60                 move.w  d4,d7                   ; d7 -> x_count
ROM:00115C62                 subq.w  #1,d7                   ; d7 -> x_count - 1
ROM:00115C64                 adda.w  d4,a0
ROM:00115C66                 adda.w  d4,a0                   ; a0 -> address of y_first (3d) or z_first (2d)
ROM:00115C68                 movea.l a0,a2                   ; a2 -> address of y_first (3d) or z_first (2d)
ROM:00115C6A
ROM:00115C6A next_x_value:
ROM:00115C6A                 cmp.w   -(a2),d2                ; a2 -> address of x_values[d7]; d2 -> x_values[d7]
ROM:00115C6C                 dbge    d7,next_x_value         ; if x_lookup < x_values[d7] then { dec d7; if d7 >= 0 then branch next_x_value }
ROM:00115C70                 bge.s   x_lower_found           ; if an x axis value lower than x_lookup (x_lower) is found then branch x_lower_found
ROM:00115C72                 clr.w   d7                      ; d7 -> 0
ROM:00115C74                 bra.s   no_x_lower              ; branch no_x_lower
ROM:00115C76 ; ---------------------------------------------------------------------------
ROM:00115C76
ROM:00115C76 x_lower_found:
ROM:00115C76                 move.w  (a2)+,d0                ; d0 low word -> x_lower; a2 -> address of x_lower + 2
ROM:00115C78                 cmpa.l  a2,a0
ROM:00115C7A                 bne.s   get_x_upper             ; if x_lower is not the last x value then branch get_x_upper
ROM:00115C7C                 subq.l  #2,a2                   ; a2 -> address of last x axis value
ROM:00115C7E
ROM:00115C7E no_x_lower:
ROM:00115C7E                 move.w  (a2),d0                 ; d0 low word -> x_lower (or x_first if no x_lower found)
ROM:00115C80
ROM:00115C80 get_x_upper:
ROM:00115C80                 swap    d0                      ; x_lower moves to d0 high word
ROM:00115C82                 move.w  (a2),d0                 ; d0 - > x_lower | x_upper
ROM:00115C84                 swap    d0                      ; d0 -> x_upper | x_lower
ROM:00115C86                 move.w  d5,d1                   ; d1 -> y_count
ROM:00115C88                 subq.w  #1,d1                   ; d1-> y_count - 1
ROM:00115C8A                 beq.w   return_ok               ; if y axis count - 1 = 0 then branch return_ok
ROM:00115C8E                 adda.w  d5,a0
ROM:00115C90                 adda.w  d5,a0                   ; a0 -> address of z_first
ROM:00115C92                 movea.l a0,a2                   ; a2 -> address of z_first
ROM:00115C94                 swap    d2                      ; x_lookup moves to d2 high word
ROM:00115C96
ROM:00115C96 next_y_value:
ROM:00115C96                 cmp.w   -(a2),d3                ; a2 -> address of y_values[d1]; compare y_values[d1] with y_lookup
ROM:00115C98                 dbge    d1,next_y_value         ; if y_lookup < y_values[d1] then { dec d1; if d1 >= 0 then branch next_y_value }
ROM:00115C9C                 bge.s   y_lower_found           ; if a y axis value lower than y_lookup (y_lower) is found then branch y_lower_found
ROM:00115C9E                 clr.w   d1                      ; d1 -> 0
ROM:00115CA0                 bra.s   no_y_lower              ; branch no_y_lower
ROM:00115CA2 ; ---------------------------------------------------------------------------
ROM:00115CA2
ROM:00115CA2 y_lower_found:
ROM:00115CA2                 move.w  (a2)+,d2                ; d2 low word -> y_lower; a2 -> address of y_lower + 2
ROM:00115CA4                 cmpa.l  a2,a0
ROM:00115CA6                 bne.s   get_y_upper             ; if y_lower is not the last y value then branch get_y_upper
ROM:00115CA8                 subq.l  #2,a2                   ; a2 -> address of last y axis value
ROM:00115CAA
ROM:00115CAA no_y_lower:
ROM:00115CAA                 move.w  (a2),d2                 ; d2 low word -> y_lower (or y_first if no y_lower found)
ROM:00115CAC
ROM:00115CAC get_y_upper:
ROM:00115CAC                 swap    d3                      ; y_lookup moves to d3 high word
ROM:00115CAE                 move.w  (a2),d3                 ; d3 -> y_lookup | y_upper
ROM:00115CB0                 muls.w  d4,d1                   ; d1 - > y_lower_idx * x_count
ROM:00115CB2                 adda.l  d1,a1                   ; a1 - > address of z_values[0, y_lower_idx]
ROM:00115CB4                 adda.w  d7,a1                   ; a1 - > address of z_values[x_lower_idx, y_lower_idx]
ROM:00115CB6                 move.l  d2,d6                   ; d6 - > x_lookup | y_lower
ROM:00115CB8                 swap    d6                      ; d6 - > y_lower | x_lookup
ROM:00115CBA                 sub.w   d0,d6                   ; d6 low word -> x_lookup - x_lower
ROM:00115CBC                 ble.s   use_x_lower             ; if x_lookup <= x_lower then branch use_x_lower
ROM:00115CBE                 move.l  d0,d5                   ; d5 - > x_upper | x_lower
ROM:00115CC0                 swap    d5                      ; d5 - > x_lower | x_upper
ROM:00115CC2                 sub.w   d0,d5                   ; d5 low word -> x_upper - x_lower
ROM:00115CC4                 beq.s   use_x_lower             ; if x_upper = x_lower then branch use_x_lower
ROM:00115CC6                 clr.w   d1                      ; d1 low word -> 0
ROM:00115CC8                 clr.w   d7                      ; d7 low word -> 0
ROM:00115CCA                 move.b  1(a1),d7                ; d7 low word => z_values[x_Lower_idx + 1, y_lower_idx]
ROM:00115CCE                 move.b  (a1),d1                 ; d1 low word => z_values[x_Lower_idx, y_lower_idx]
ROM:00115CD0                 sub.w   d1,d7                   ; d7 low word => z_values[x_Lower_idx + 1, y_lower_idx] - d7 => z_values[x_Lower_idx, y_lower_idx]
ROM:00115CD2                 beq.s   no_z_delta_lower        ; if no z delta over x for y_lower_idx then branch no_z_delta_lower
ROM:00115CD4                 muls.w  d6,d7                   ; d7 low word -> (z_values[x_lower_idx + 1, y_lower_idx] - z_values[x_lower_idx, y_lower_idx]) * (x_lookup - x_lower)
ROM:00115CD6                 divs.w  d5,d7                   ; d7 low word -> (z_values[x_lower_idx + 1, y_lower_idx] - z_values[x_lower_idx, y_lower_idx]) * (x_lookup - x_lower) / (x_upper - x_lower)
ROM:00115CD8
ROM:00115CD8 no_z_delta_lower:
ROM:00115CD8                 add.b   (a1),d7                 ; d7 low word -> z_values[x_lower_idx, y_lower_idx] + (z_values[x_lower_idx + 1, y_lower_idx] - z_values[x_lower_idx, y_lower_idx]) * (x_lookup - x_lower) / (x_upper - x_lower)
ROM:00115CDA                 clr.w   d0                      ; d0 low word -> 0
ROM:00115CDC                 clr.w   d1                      ; d1 low word -> 0
ROM:00115CDE                 move.b  1(a1,d4.w),d1           ; d1 low word -> z_values[x_lower_idx + 1, y_lower_idx + 1]; NB: This may overflow end of table. If so calculates invalid data here and discards later!
ROM:00115CE2                 move.b  (a1,d4.w),d0            ; d0 low word -> z_values[x_lower_idx, y_lower_idx + 1]; NB: This may overflow end of table. If so calculates invalid data here and discards later!
ROM:00115CE6                 sub.w   d0,d1                   ; d1 low word -> z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]; NB: This may overflow end of table. If so calculates invalid data here and discards later!
ROM:00115CE8                 beq.s   no_z_delta_upper        ; if no z delta over x for y_lower_idx + 1 then branch no_z_delta_upper
ROM:00115CEA                 muls.w  d6,d1                   ; d1 low word -> (z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]) * (x_lookup - x_lower)
ROM:00115CEC                 divs.w  d5,d1                   ; d1 low word -> (z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]) * (x_lookup - x_lower) / (x_upper - x_lower)
ROM:00115CEE
ROM:00115CEE no_z_delta_upper:
ROM:00115CEE                 add.b   (a1,d4.w),d1            ; d1 low word -> z_values[x_lower_idx, y_lower_idx + 1] + (z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]) * (x_lookup - x_lower) / (x_upper - x_lower)
ROM:00115CF2                 bra.s   interp_on_y             ; branch interp_on_y
ROM:00115CF4 ; ---------------------------------------------------------------------------
ROM:00115CF4
ROM:00115CF4 use_x_lower:
ROM:00115CF4  
ROM:00115CF4                 move.b  (a1),d7                 ; d7 low word -> z_values[x_lower_idx, y_lower_idx]
ROM:00115CF6                 move.b  (a1,d4.w),d1            ; d1 low word -> z_values[x_lower_idx, y_lower_idx + 1]; NB: This may overflow end of table. If so calculates invalid data here and discards later!
ROM:00115CFA
ROM:00115CFA interp_on_y:
ROM:00115CFA                 move.l  d3,d6                   ; d6 -> y_lookup | y_upper
ROM:00115CFC                 swap    d6                      ; d6 -> y_upper | y_lookup
ROM:00115CFE                 sub.w   d2,d6                   ; d6 low word -> y_lookup - y_lower
ROM:00115D00                 ble.s   use_y_lower             ; if y_lookup <= y_lower then branch use_y_lower
ROM:00115D02                 move.w  d3,d5                   ; d5 low word -> y_upper
ROM:00115D04                 sub.w   d2,d5                   ; d5 low word -> y_upper - y_lower
ROM:00115D06                 beq.s   use_y_lower             ; if y_upper = y_lower then branch use_y_lower
ROM:00115D08                 andi.w  #$FF,d7                 ; d7 low word -> d7 low byte
ROM:00115D0C                 andi.w  #$FF,d1                 ; d1 low word -> d1 low byte
ROM:00115D10                 sub.w   d7,d1
ROM:00115D12                 beq.s   use_y_lower             ; if no z delta over y between interpolations over x then branch use_y_lower
ROM:00115D14                 muls.w  d6,d1                   ; d1 low word -> z_values[x_lower_idx, y_lower_idx + 1] + (z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]) * (x_lookup - x_lower) / (x_upper - x_lower) * (y_lookup - y_lower)
ROM:00115D16                 divs.w  d5,d1                   ; d1 low word -> z_values[x_lower_idx, y_lower_idx + 1] + (z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]) * (x_lookup - x_lower) / (x_upper - x_lower) * (y_lookup - y_lower) / (y_lookup - y_lower)
ROM:00115D18                 add.b   d7,d1
ROM:00115D1A                 andi.w  #$FF,d1                 ; d1 low word -> z_values[x_lower_idx, y_lower_idx + 1] + (z_values[x_lower_idx + 1, y_lower_idx + 1] - z_values[x_lower_idx, y_lower_idx + 1]) * (x_lookup - x_lower) / (x_upper - x_lower) * (y_lookup - y_lower) / (y_lookup - y_lower) + z_values[x_lower_idx, y_lower_idx] + (z_values[x_lower_idx + 1, y_lower_idx] - z_values[x_lower_idx, y_lower_idx]) * (x_lookup - x_lower) / (x_upper - x_lower)
ROM:00115D1E                 bra.s   return_ok               ; branch return_ok
ROM:00115D20 ; ---------------------------------------------------------------------------
ROM:00115D20
ROM:00115D20 use_y_lower:
ROM:00115D20  
ROM:00115D20                 move.w  d7,d1                   ; d1 -> z_values[x_lower_idx, y_lower_idx] + (z_values[x_lower_idx + 1, y_lower_idx] - z_values[x_lower_idx, y_lower_idx]) * (x_lookup - x_lower) / (x_upper - x_lower)
ROM:00115D22
ROM:00115D22 return_ok:
ROM:00115D22  
ROM:00115D22                 clr.l   d0                      ; do -> #0; indicates success
ROM:00115D24                 bra.s   return                  ; branch return
ROM:00115D26 ; ---------------------------------------------------------------------------
ROM:00115D26
ROM:00115D26 return_error:
ROM:00115D26  
ROM:00115D26                 move.b  #$FF,d0                 ; do -> #$ff; indicates failure
ROM:00115D2A
ROM:00115D2A return:
ROM:00115D2A                 rts                             ; return from subroutine
ROM:00115D2A ; End of function Lookup_Table_0
ROM:00115D2A
ROM:00115D2C