Go deh!: 2-Dimension matrix to 1-D array, index translations.

Work has me working with hardware registers. Many registers; arrayed registers; multi-arrayed registers!.

The verifiction library I use has code to handle 1-D arrays of registers but not for 2-d (matrix) of registers - which is the problem I have today.

Problem Statement

A useful description of the problem is:
Given a 2-D matrix of values to store and access in a system that allows the storingof 1-D arrays of values, how do you map from the 2-D x,y indices to the 1-D i index - and vice-versa?

Partial memory

It's several decades since I first looked into this but I do remember divmod! Divmod was a part of the solution: divmod(x, y) returns (x // y, x % y) i.e the integer divisor and the integer remainder of x and y, as a tuple.

Rather than "do the math" to work out the correct functions needed to generate a 1-D array index i, from two matrix indices x and y - as well as the reverse function - I decided to take a suck-it-and-see approach. I had ideas that contain the correct solution and devised tests to reject faulty implementations.

Setup

Indices in any dimension count up from zero.
Use a different maximum index in each matrix dimension to aid later checks
I created function irange (line 14+), as sometimes people like to generate integer ranges that include both endpoints.

1-D to 2-D

Variable i_to_xy_list on lines 35+, has the source for four functions alternatives that when given a 1-D index generate a tuple of index numbers representing x and y. All four use divmod.

To test them I create a python function from the text using eval in line 50 then, knowing that if the matrix has three possible x values and four possible y values and so indexes exactly 3*4 = 24 values, I use a range of 1-D index of 0-to-23 inclsive to hold the corresponding x,y tuples generated, in the (oredered) dict dim_1 in line 52.
Sets all_xy, all_x, and all_y (lines54-56), accumulate the different indexing number-pairs and numbers seen in all/each dimension of the matrix indexing generated from this function i2xy. They are then tested to ensure they have the expected number and range of individual indeces
in lines 57-68.

2-D to 1-D

Similarly xy_to_i_list has four possible ways that could match-up with a passing 1-D to 2-D fnction to do the reverse conversion from x,y coords to linear array index i.
all permutations of the range of x and y index values are used to generate sample 1-D indeces in dict dim_n (line 73), then the generated 1-D indices are checked (line 76+)

The last check, from line 86, checks that the i2xy function and xy2i functions are inverses of each other, generating and decoding the same indeces.

The output

## ORIGINAL 2-D ARRAY:
0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3

  # TRIAL MAPPINGS TO 1-D ARRAY
  FAIL! x count from `x, y = (lambda index_i: divmod(index_i, xcount))(index_i)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x * xcount + y)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x + y * ycount)(x, y)`
  FAIL! Mapping index_i to/from x, y using `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x * xcount + y)(x, y)`
  FAIL! Mapping index_i to/from x, y using `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x + y * ycount)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`
  FAIL! x count from `x, y = (lambda index_i: divmod(index_i, ycount)[::-1])(index_i)`

# SUMMARY
  PASS! `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`

Or to rewrite the lambdas as functions:

# These two:
def i2xy(i):
    return divmod(i, ycount)
def xy2i(x, y):
    return x * ycount + y
# Or these two:
def i2xy(i):
    return reversed(divmod(i, xcount))
def xy2i(x, y):
    return x + y * xcount

Code:

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 24 21:31:03 2019

@author: Paddy3118
"""

from collections import OrderedDict
from itertools import product
from pprint import pprint as pp

#%%

def irange(mini, maxi):
    "Integer range mini-to-maxi inclusive of _both_ endpoints"
    # Some think ranges should include _both_ endpoints, oh well.
    return range(mini, maxi+1)

#%%
xrange = irange(0, 2)
yrange = irange(0, 3)
xcount = len(xrange) # 3
ycount = len(yrange) # 4

print("\n## ORIGINAL 2-D ARRAY:")
for x in xrange:
    print(' '.join(f"{x},{y}" for y in yrange))


#%%
print("\n  # TRIAL MAPPINGS TO 1-D ARRAY")
print_on_fail, print_on_pass = False, False

# Possible ways to get what n-dimensional index-tuple is stored at linear index
i_to_xy_list = """
lambda index_i: divmod(index_i, xcount)
lambda index_i: divmod(index_i, ycount)
lambda index_i: divmod(index_i, xcount)[::-1]
lambda index_i: divmod(index_i, ycount)[::-1]
""".strip().split('\n')
# Possible ways to generate a linear 1-D index from n-D tuple of indices
xy_to_i_list = """
lambda x, y: x * xcount + y
lambda x, y: x * ycount + y
lambda x, y: x + y * ycount
lambda x, y: x + y * xcount
""".strip().split('\n')
passes = []
for i_to_xy in i_to_xy_list:
    i2xy = eval(i_to_xy)
    # Representing a 1-D array as OrderedDict preserves insertion order
    dim_1 = OrderedDict((index_i, i2xy(index_i)) 
                        for index_i in irange(0, xcount*ycount - 1))
    all_xy = set(dim_1.values())
    all_x  = set(x for x, y in dim_1.values())
    all_y  = set(y for x, y in dim_1.values())
    if len(all_xy) != xcount * ycount:
        print(f"  FAIL! x,y count from `x, y = ({i_to_xy})(index_i)`")
        if print_on_fail: pp(dim_1)
        continue
    if len(all_x) != xcount:
        print(f"  FAIL! x count from `x, y = ({i_to_xy})(index_i)`")
        if print_on_fail: pp(dim_1)
        continue
    if len(all_y) != ycount:
        print(f"  FAIL! y count from `x, y = ({i_to_xy})(index_i)`")
        if print_on_fail: pp(dim_1)
        continue
    #
    for xy_to_i in xy_to_i_list:
        xy2i = eval(xy_to_i)
        # Representing a N-D array
        dim_n = OrderedDict(((x, y), xy2i(x, y))
                            for x, y in product(xrange, yrange))
        all_i = set(dim_n.values())
        if min(all_i) != 0:
            print(f"  FAIL! Min index_i not zero in "
                  f"`index_i = ({xy_to_i})(x, y)`")
            if print_on_fail: pp(dim_n)
            continue
        if max(all_i) != xcount * ycount - 1:
            print(f"  FAIL! Max index_i not {xcount * ycount - 1} in "
                  f"`index_i = ({xy_to_i})(x, y)`")
            if print_on_fail: pp(dim_n)
            continue
        if not all(dim_1[dim_n[xy]] == xy
                   for xy in dim_n):
            print(f"  FAIL! Mapping index_i to/from x, y using "
                  f"`x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`")
            if print_on_fail: pp(dim_1)
            if print_on_fail: pp(dim_n)
            continue
        passes.append((i_to_xy, xy_to_i))
        print(f"  PASS! `x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`")
        if print_on_pass:
            pp(dim_1)
            pp(dim_n)

print('\n# SUMMARY')
for i_to_xy, xy_to_i in passes:
    print(f"  PASS! `x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`")
#

Go deh!

Monday, August 26, 2019

2-Dimension matrix to 1-D array, index translations.