Tuesday, August 27, 2019

N-Dimensional matrix to 1-D array indexing translations.


Having done the 2-D address indexing translations, I thught about how to translate between a set of 3-D indices and a linear 1-D array index then extrapolated to n-dimensions.

I liked the idea of testing the solution and have brought that across too (with additions)

The class

1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42

# -*- coding: utf-8 -*-
"""
Created on Tue Aug 27 01:49:51 2019

@author: Paddy3118
"""

from collections import OrderedDict
from itertools import product
from functools import reduce

#%%

class ND21D_Addressing():
    """
    Convert n-dimensional indexing to/from 1-D index as if packed  
    into 1-D array. 
    All indices assumed to start from zero
    """
    def __init__(self, *extent):
        "extent is tuple of index sizes in each dimension"
        n_dim = len(extent) # Dimensionality
        self._extent = extent
        self._offsets = [reduce(int.__mul__, 
                               extent[n + 1:], 1) 
                        for n in range(n_dim)]

    # What n-dimensional index-tuple is stored at linear index.
    def i2ndim(self, index_i):
        "1-D array index to to n-D tuple of indices"
        return tuple((index_i // s) % c 
                     for s, c in zip(self._offsets, self._extent))
    
    # What linear 1-D index stores n-D tuple of indices.
    def ndim2i(self, ni):
        "n-D tuple of indices to 1-D array index"
        return sum(d * s for s, d in zip(self._offsets, ni))
    
    def __repr__(self):
        return f"{self.__class__.__name__}({str(self._extent)[1:-1]})"
#%%
    


The test

43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
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)

def _print_n_dim(ranges_from_zero):
    "Represent the indexing of an n-D matrix"
    last = [0] * len(ranges_from_zero)
    for ni in product(*ranges_from_zero):
        for s, t in zip(last, ni):
            if s != t and t == 0: print()
        last = ni
        print(str(ni).replace(' ', ''), end=' ')
    print()

#%%
if __name__ == "__main__":
    # Dimensionality for test
    n_dim = 4
    
    # range of values in each dimension.
    dranges = [_irange(0, d+1) for d in range(n_dim)]
    # Num of values in each dim.
    extent = [len(dr) for dr in dranges]  
    
    ## The address mapper instance
    admap = ND21D_Addressing(*extent)
    
    ## A test matrix of given dimensionality
    # Optimum size of mapping to 1-dim. array
    size_1d = reduce(int.__mul__, extent)  
    # Range of all mapped to 1-dim. array index values
    range_1d = _irange(0, size_1d - 1)  

    print(f"\n## ORIGINAL {n_dim}-D ARRAY:")
    _print_n_dim(dranges)

    print(f"\n# TEST TRIAL MAP {n_dim}-D TO/FROM 1-D ARRAY ADDRESSING")
          
    # Representing a 1-D array mapped to n-D index tuple 
    dim_1 = OrderedDict((index_i, admap.i2ndim(index_i)) 
                        for index_i in range_1d)
    all_ndim = set(dim_1.values())
    all_by_dim  = [set(d1) for d1 in zip(*all_ndim)]
    assert len(all_ndim) == size_1d, "FAIL! ndim index count"
    for a_dim, its_count in zip(all_by_dim, extent):
        assert len(set(a_dim)) == its_count, \
               "FAIL! ndim individual index count"
               
    # Representing n-D index tuple mapped to 1-D index
    dim_n = OrderedDict(((ndim), admap.ndim2i(ndim))
                        for ndim in product(*dranges))
    all_i = set(dim_n.values())
    assert min(all_i) == 0, "FAIL! Min index_i not zero"
    assert max(all_i) == size_1d - 1, \
           f"FAIL! Max index_i not {size_1d - 1}"

    # Check inverse mappings
    assert all(dim_1[dim_n[ndim]] == ndim 
               for ndim in dim_n), \
           "FAIL! Mapping n-D to/from 1-D indices"
    assert all(dim_n[dim_1[index_i]] == index_i 
               for index_i in range_1d), \
           "FAIL! Mapping 1-D to/from n-D indices"

    print(f"  {admap}: PASS!")



The test output


## ORIGINAL 4-D ARRAY:
(0,0,0,0) (0,0,0,1) (0,0,0,2) (0,0,0,3) (0,0,0,4) 
(0,0,1,0) (0,0,1,1) (0,0,1,2) (0,0,1,3) (0,0,1,4) 
(0,0,2,0) (0,0,2,1) (0,0,2,2) (0,0,2,3) (0,0,2,4) 
(0,0,3,0) (0,0,3,1) (0,0,3,2) (0,0,3,3) (0,0,3,4) 

(0,1,0,0) (0,1,0,1) (0,1,0,2) (0,1,0,3) (0,1,0,4) 
(0,1,1,0) (0,1,1,1) (0,1,1,2) (0,1,1,3) (0,1,1,4) 
(0,1,2,0) (0,1,2,1) (0,1,2,2) (0,1,2,3) (0,1,2,4) 
(0,1,3,0) (0,1,3,1) (0,1,3,2) (0,1,3,3) (0,1,3,4) 

(0,2,0,0) (0,2,0,1) (0,2,0,2) (0,2,0,3) (0,2,0,4) 
(0,2,1,0) (0,2,1,1) (0,2,1,2) (0,2,1,3) (0,2,1,4) 
(0,2,2,0) (0,2,2,1) (0,2,2,2) (0,2,2,3) (0,2,2,4) 
(0,2,3,0) (0,2,3,1) (0,2,3,2) (0,2,3,3) (0,2,3,4) 


(1,0,0,0) (1,0,0,1) (1,0,0,2) (1,0,0,3) (1,0,0,4) 
(1,0,1,0) (1,0,1,1) (1,0,1,2) (1,0,1,3) (1,0,1,4) 
(1,0,2,0) (1,0,2,1) (1,0,2,2) (1,0,2,3) (1,0,2,4) 
(1,0,3,0) (1,0,3,1) (1,0,3,2) (1,0,3,3) (1,0,3,4) 

(1,1,0,0) (1,1,0,1) (1,1,0,2) (1,1,0,3) (1,1,0,4) 
(1,1,1,0) (1,1,1,1) (1,1,1,2) (1,1,1,3) (1,1,1,4) 
(1,1,2,0) (1,1,2,1) (1,1,2,2) (1,1,2,3) (1,1,2,4) 
(1,1,3,0) (1,1,3,1) (1,1,3,2) (1,1,3,3) (1,1,3,4) 

(1,2,0,0) (1,2,0,1) (1,2,0,2) (1,2,0,3) (1,2,0,4) 
(1,2,1,0) (1,2,1,1) (1,2,1,2) (1,2,1,3) (1,2,1,4) 
(1,2,2,0) (1,2,2,1) (1,2,2,2) (1,2,2,3) (1,2,2,4) 
(1,2,3,0) (1,2,3,1) (1,2,3,2) (1,2,3,3) (1,2,3,4) 

# TEST TRIAL MAP 4-D TO/FROM 1-D ARRAY ADDRESSING
  ND21D_Addressing(2, 3, 4, 5): PASS!


END.

Monday, August 26, 2019

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

  1. Indices in any dimension count up from zero.
  2. Use a different maximum index in each matrix dimension to aid later checks
  3. 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:

1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
# -*- 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)`")
#