# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## 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)`") # ```