Velocity Reviews > Dynamic indexing (multi-dimensional-indexing) (probably my most important/valuable posting up to this date)

# Dynamic indexing (multi-dimensional-indexing) (probably my most important/valuable posting up to this date)

Skybuck Flying
Guest
Posts: n/a

 07-01-2011
This is probably the most important test/demonstration program I ever wrote
and published/released onto the internet (up to this date (7 juli 2011)).

I hope compiler writers/programming language designers will study it
carefully and integrate it into their language.
(It's a bit long/lengthy read by well worth it ! Also casual programmers can
benefit from it as well !)

See comments for more details about the usefullness and the value of it for
present day and the future.

Also see test program way down below for usage example and verification
program.

Especially the formula's are very important.

"dynamic pointer indexing"

Which takes this step a bit further to provide direct memory access
(concept/thread which is still under development).

This posting takes a step back to evaluate and verify the formula's to be
used in "dynamic pointer indexing".

For now this example/concept can be thought of as "dynamic indexing".

Which can also be thought of as "multi-dimensional indexing".

A future which is currently missing in C/C++/CUDA C/C++ and in a way also
Delphi since Delphi requires a pointer array per additional dimension.

The technique illustrated below needs none of that Delphi overhead and
introduces it's own much smaller overhead, memory-wise, it does introduce a

There is also a hidden potential problem if parenthesis would be used.

A small explanation for the people that did not follow the other thread
mentioned:

The multiply operator is used as a passing mechanism to calculate a linear
index for the multi dimension indexes.

// *** Begin of Program ***

program TestProgram;

{\$APPTYPE CONSOLE}

{

Test dynamic multi dimensional index calculations

version 0.01 created on 1 juli 2011 by Skybuck Flying

To illustrate the theory behind dynamic multi dimension index calculations I
shall now
create a little test/demonstration program to show you how to write this
code and what
formula's to use.

The example deviates from the written theory so far in regard to the order,
the order
in the theory was assumed to be z, y, x however delphi's order appears to be
x, y, z.

Therefore the formula's will be adepted to Delphi's order.

For completeness sakes I shall mention the formula's in this comments one
more time.

How these formula's where derived I will not explain here because it was a
bit vague and messy but all in all not to bad.
But you don't need to know that... all that matters are the formula's you
can probably derive/come to the conclusion
how these were formed yourself and if not consider these a gift to you from
me !

Formula for index calculation in abstract form:

result.index =
(lower dimension parameter.index * lower dimension parameter.stride) +
(higher dimension parameter.index * lower dimension parameter.volume);

the resulting stride should be 1 until further notice
result.stride = 1;

Valueable notes for you to understand:

Strides always have a minimum of 1.
Volumes always have a minimum of 1.
DimensionCounts always have a minimum of 1.

These ones assure that none of the multiplications are zero-ed out, that
This is why these general formula's work. No matter if the stride is 1 and
the volume is 1 it will still work.
So some unnecessary multiplications with 1 might be done but so be it for
generalities sake.

The last formula you will need is the volume calculation in abstract form
which is actually quite simply:

result.volume = (lower dimension parameter.volume * higher dimension
parameter.volume);

It should be apperent to you now why this will work, but I shall explain it
anyway.

Since the order is from left to right which means low to high this will
work.

The lowest dimension is multiplied with the higher dimension giving a new
volume, in the first two dimension case
this would be the area (a volume with a depth of 1) the next dimension it is
multiplied with would give a new volume.
(a real 3d volume with a depth of depth). The next dimension it is
multiplied against gives a 4D volume. I use
the term "volume" for a lack of a better term for a 4D quanitity. So think
of a volume is that which describes
the entire (coordinate) space (or index space if you will).

I shall also give these two formula's in a somewhat more concrete and short
hand form for direct/easy/correct implementation purposes:

result.stride := 1;
result.index := (ParaA.Index * ParaA.Stride) + (ParaB.Index * ParaA.Volume);
result.volume := (ParaA.Volume * ParaB.Volume);

Now it's time for a test/demonstration program to proof to you that this is
not bullshit, to prove to you that is is valuable
and that this works and to show the power/flexibility of it so you will
hopefully see how usefull this would become
if this became a primary language feature with further support behind it !
=D

However the current code which shall be provided can already be of high
value for current day usasage ! =D

To show the usefullness of it a type will be introduced which shall
encompass this theory and these formula's.

This type shall be called "TDynamicIndex" it's purposes is many-fold:

To construct "dynamic" multi dimensional array indexing automatically.

So that the user programmer can easily adjust it's code to support all kinds
of 1D, 2D, 3D and xD dimensions.

Possibly layed out over a single dimension.

So this type calculates a linear index (which is the final/result index)
which can then be used to access for example
the memory system (which is a 1D entity).

Also to simply the design, the indexed property will be replaced with a
procedure, this illustrates
that the method is applieable to other languages which do not have
properties like c/c++, so this also illustrates
that the method works not because of properties but thanks to operator

However I have no way of setting the index value with indexed properties (a
procedure call would look ugly so I am going
to leave it in ! ) but rename it also a little bit to show what it does.

This test/demonstration program will also function as a verifier to verify
that the calculations are indeed correct.

Conclusion:

It works flawlessly so far.

This is probably one of the, if not the, most important test program and
theory I have ever published.

I hope compiler writers will study it carefully and will hopefully be able
to integrate this "technology" into
their programming languages so that we programmers can finally use "dynamic
pointers" and "dynamic indexes".. so
that we programmers can finally program easily in multiple dimensions which
translate to a linear/1d dimension for memory access.

So that we can finally have multi dimensional array indexing with paying
penalties like additional pointers or difficult data
structure construction involving multiple array creations and such.

This demonstration and code will become more valuable as CUDA/OpenCL becomes
more valuable and widely used.

CUDA C/C++ is a perfect example of the
"multi dimensional indexing hell/linear index calculation hell, problem
distribution hell" that CUDA C/C++ programmers are now facing.

This code demonstration demonstrates how to solve it in a flexible way.

The usage example is hard coded to use the dimensions of x: 320 y: 200 z: 60
which represents the classic ms-dos vga
screen and a refresh rate of 60, (which was actually 70 at the time but ok),
so some programmers might be used to these dimensions
and might recgonize some of it.

Hopefully needless to say, this example is not limited to these dimensions,
and any dimension can be used.

A word of caution: integer has been used for volume. It's pretty easy to see
how the volume calculation might overflow
for large dimensions so keep an eye out of that. For now I shall let it be
an integer for speed's sake.

If an overflow occurs for your usage consider using an int64 for larger
dimension support.

This demonstration code has limited itself to indexes to keep things simple.

Strides have also been set to 1.

This represent a byte.

Changing the stride to 4 would represent an integer.

Only the first stride for the X dimension would need to be set to 4.

The other strides should be left alone and be set to 1.

Changing the stride would invalidate the verification program ofcourse.

Changing the code to automatically adept to changes should be obvious, but
for clearities sake
will not be done in version 0.01.

Perhaps version 0.02 might do this, but for now I see little value in it !

I shall now continue working on my TDynamicPointer concept which uses
the concepts presented here in TDynamicIndex and expands on it to support

}

uses
SysUtils;

type
TDynamicIndex = record
private
mIndex : integer;
mStride : integer;
mDimensionCount : integer;
mVolume : integer;

function StoreIndex( ParaIndex : integer ) : TDynamicIndex;
public
constructor Create( ParaDimensionCount : integer; ParaStride : integer );

property IndexOperator[ ParaIndex : integer ] : TDynamicIndex read
StoreIndex; default;

class operator Multiply( ParaA, ParaB : TDynamicIndex ) : TDynamicIndex;
end;

constructor TDynamicIndex.Create( ParaDimensionCount : integer; ParaStride :
integer );
begin
mIndex := 0;
mStride := 1;
mDimensionCount := 1;
mVolume := 1;

begin
end;

if ParaStride > 1 then
begin
mStride := ParaStride;
end;

mVolume := mDimensionCount * mStride;
end;

// store index, and return a copy, not because we want to, but because we
must
// I would much rather return a pointer, but unfortunately calling multiple
operator on pointer derefence won't work well ?!)
// perhaps it should be retried sometime...
function TDynamicIndex.StoreIndex( ParaIndex : integer ) : TDynamicIndex;
begin
mIndex := ParaIndex;
result.mIndex := mIndex;
result.mStride := mStride;
result.mDimensionCount := mDimensionCount;
result.mVolume := mVolume;
end;

class operator TDynamicIndex.Multiply( ParaA, ParaB : TDynamicIndex ) :
TDynamicIndex;
begin
result.mStride := 1;
result.mIndex := (ParaA.mIndex * ParaA.mStride) + (ParaB.mIndex *
ParaA.mVolume);
result.mVolume := (ParaA.mVolume * ParaB.mVolume);
end;

procedure Main;
var
X : TDynamicIndex;
Y : TDynamicIndex;
Z : TDynamicIndex;
Result : TDynamicIndex;
vErrorDetected : boolean;

vX : integer;
vY : integer;
vZ : integer;

vCheck : integer;
begin
X := TDynamicIndex.Create( 320, 1 );
Y := TDynamicIndex.Create( 200, 1 );
Z := TDynamicIndex.Create( 60, 1 );

// first a few single tests to see/show how it works.
Result := X[ 0 ] * Y[ 0 ] * Z[ 1 ]; // should display 320*200*1*1=64000
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 0 ] * Z[ 0 ]; // should display 319*1*1*1=319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100 ] * Z[ 0 ]; // should display 319*1 +
(100*320)*1*1 = 32319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100 ] * Z[ 5 ]; // should display 319*1 +
(100*320)*1 + (5*200*320)*1 = 32319 + 320000 = 352319
writeln( Result.mIndex );

// so far so could so now let's do some exhaustive/full verifications.
writeln('Verification started.');

vErrorDetected := false;
for vZ := 0 to 59 do
begin
for vY := 0 to 199 do
begin
for vX := 0 to 319 do
begin
Result := X[ vX ] * Y[ vY ] * Z[ vZ ];

vCheck := (vZ * 200 * 320) + (vY * 320) + vX;

if Result.mIndex <> vCheck then
begin
writeln('Index calculation error detected at (vX, vY, vZ): ' + '(' +
IntToStr(vX) + ',' + IntToStr(vY) + ',' + IntToStr(vZ) + ')' );
vErrorDetected := true;
end;
end;
end;
end;

writeln('Verification done.');

if vErrorDetected then
begin
writeln('Verification result: errors detected !');
end else
begin
writeln('Verification result: no errors detected.');
end;
end;

begin
try
Main;
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
end.

// *** End of Program ***

Bye,
Skybuck.

Skybuck Flying
Guest
Posts: n/a

 07-01-2011
Little typo corrected at (*****) (with changed to without):

This is probably the most important test/demonstration program I ever wrote
and published/released onto the internet (up to this date (7 juli 2011)).

I hope compiler writers/programming language designers will study it
carefully and integrate it into their language.
(It's a bit long/lengthy read by well worth it ! Also casual programmers can
benefit from it as well !)

See comments for more details about the usefullness and the value of it for
present day and the future.

Also see test program way down below for usage example and verification
program.

Especially the formula's are very important.

"dynamic pointer indexing"

Which takes this step a bit further to provide direct memory access
(concept/thread which is still under development).

This posting takes a step back to evaluate and verify the formula's to be
used in "dynamic pointer indexing".

For now this example/concept can be thought of as "dynamic indexing".

Which can also be thought of as "multi-dimensional indexing".

A future which is currently missing in C/C++/CUDA C/C++ and in a way also
Delphi since Delphi requires a pointer array per additional dimension.

The technique illustrated below needs none of that Delphi overhead and
introduces it's own much smaller overhead, memory-wise, it does introduce a

There is also a hidden potential problem if parenthesis would be used.

A small explanation for the people that did not follow the other thread
mentioned:

The multiply operator is used as a passing mechanism to calculate a linear
index for the multi dimension indexes.

// *** Begin of Program ***

program TestProgram;

{\$APPTYPE CONSOLE}

{

Test dynamic multi dimensional index calculations

version 0.01 created on 1 juli 2011 by Skybuck Flying

To illustrate the theory behind dynamic multi dimension index calculations I
shall now
create a little test/demonstration program to show you how to write this
code and what
formula's to use.

The example deviates from the written theory so far in regard to the order,
the order
in the theory was assumed to be z, y, x however delphi's order appears to be
x, y, z.

Therefore the formula's will be adepted to Delphi's order.

For completeness sakes I shall mention the formula's in this comments one
more time.

How these formula's where derived I will not explain here because it was a
bit vague and messy but all in all not to bad.
But you don't need to know that... all that matters are the formula's you
can probably derive/come to the conclusion
how these were formed yourself and if not consider these a gift to you from
me !

Formula for index calculation in abstract form:

result.index =
(lower dimension parameter.index * lower dimension parameter.stride) +
(higher dimension parameter.index * lower dimension parameter.volume);

the resulting stride should be 1 until further notice
result.stride = 1;

Valueable notes for you to understand:

Strides always have a minimum of 1.
Volumes always have a minimum of 1.
DimensionCounts always have a minimum of 1.

These ones assure that none of the multiplications are zero-ed out, that
This is why these general formula's work. No matter if the stride is 1 and
the volume is 1 it will still work.
So some unnecessary multiplications with 1 might be done but so be it for
generalities sake.

The last formula you will need is the volume calculation in abstract form
which is actually quite simply:

result.volume = (lower dimension parameter.volume * higher dimension
parameter.volume);

It should be apperent to you now why this will work, but I shall explain it
anyway.

Since the order is from left to right which means low to high this will
work.

The lowest dimension is multiplied with the higher dimension giving a new
volume, in the first two dimension case
this would be the area (a volume with a depth of 1) the next dimension it is
multiplied with would give a new volume.
(a real 3d volume with a depth of depth). The next dimension it is
multiplied against gives a 4D volume. I use
the term "volume" for a lack of a better term for a 4D quanitity. So think
of a volume is that which describes
the entire (coordinate) space (or index space if you will).

I shall also give these two formula's in a somewhat more concrete and short
hand form for direct/easy/correct implementation purposes:

result.stride := 1;
result.index := (ParaA.Index * ParaA.Stride) + (ParaB.Index * ParaA.Volume);
result.volume := (ParaA.Volume * ParaB.Volume);

Now it's time for a test/demonstration program to proof to you that this is
not bullshit, to prove to you that is is valuable
and that this works and to show the power/flexibility of it so you will
hopefully see how usefull this would become
if this became a primary language feature with further support behind it !
=D

However the current code which shall be provided can already be of high
value for current day usasage ! =D

To show the usefullness of it a type will be introduced which shall
encompass this theory and these formula's.

This type shall be called "TDynamicIndex" it's purposes is many-fold:

To construct "dynamic" multi dimensional array indexing automatically.

So that the user programmer can easily adjust it's code to support all kinds
of 1D, 2D, 3D and xD dimensions.

Possibly layed out over a single dimension.

So this type calculates a linear index (which is the final/result index)
which can then be used to access for example
the memory system (which is a 1D entity).

Also to simply the design, the indexed property will be replaced with a
procedure, this illustrates
that the method is applieable to other languages which do not have
properties like c/c++, so this also illustrates
that the method works not because of properties but thanks to operator

However I have no way of setting the index value with indexed properties (a
procedure call would look ugly so I am going
to leave it in ! ) but rename it also a little bit to show what it does.

This test/demonstration program will also function as a verifier to verify
that the calculations are indeed correct.

Conclusion:

It works flawlessly so far.

This is probably one of the, if not the, most important test program and
theory I have ever published.

I hope compiler writers will study it carefully and will hopefully be able
to integrate this "technology" into
their programming languages so that we programmers can finally use "dynamic
pointers" and "dynamic indexes".. so
that we programmers can finally program easily in multiple dimensions which
translate to a linear/1d dimension for memory access.

So that we can finally have multi dimensional array indexing without (*****)
paying
penalties like additional pointers or difficult data
structure construction involving multiple array creations and such.

This demonstration and code will become more valuable as CUDA/OpenCL becomes
more valuable and widely used.

CUDA C/C++ is a perfect example of the
"multi dimensional indexing hell/linear index calculation hell, problem
distribution hell" that CUDA C/C++ programmers are now facing.

This code demonstration demonstrates how to solve it in a flexible way.

The usage example is hard coded to use the dimensions of x: 320 y: 200 z: 60
which represents the classic ms-dos vga
screen and a refresh rate of 60, (which was actually 70 at the time but ok),
so some programmers might be used to these dimensions
and might recgonize some of it.

Hopefully needless to say, this example is not limited to these dimensions,
and any dimension can be used.

A word of caution: integer has been used for volume. It's pretty easy to see
how the volume calculation might overflow
for large dimensions so keep an eye out of that. For now I shall let it be
an integer for speed's sake.

If an overflow occurs for your usage consider using an int64 for larger
dimension support.

This demonstration code has limited itself to indexes to keep things simple.

Strides have also been set to 1.

This represent a byte.

Changing the stride to 4 would represent an integer.

Only the first stride for the X dimension would need to be set to 4.

The other strides should be left alone and be set to 1.

Changing the stride would invalidate the verification program ofcourse.

Changing the code to automatically adept to changes should be obvious, but
for clearities sake
will not be done in version 0.01.

Perhaps version 0.02 might do this, but for now I see little value in it !

I shall now continue working on my TDynamicPointer concept which uses
the concepts presented here in TDynamicIndex and expands on it to support

}

uses
SysUtils;

type
TDynamicIndex = record
private
mIndex : integer;
mStride : integer;
mDimensionCount : integer;
mVolume : integer;

function StoreIndex( ParaIndex : integer ) : TDynamicIndex;
public
constructor Create( ParaDimensionCount : integer; ParaStride : integer );

property IndexOperator[ ParaIndex : integer ] : TDynamicIndex read
StoreIndex; default;

class operator Multiply( ParaA, ParaB : TDynamicIndex ) : TDynamicIndex;
end;

constructor TDynamicIndex.Create( ParaDimensionCount : integer; ParaStride :
integer );
begin
mIndex := 0;
mStride := 1;
mDimensionCount := 1;
mVolume := 1;

begin
end;

if ParaStride > 1 then
begin
mStride := ParaStride;
end;

mVolume := mDimensionCount * mStride;
end;

// store index, and return a copy, not because we want to, but because we
must
// I would much rather return a pointer, but unfortunately calling multiple
operator on pointer derefence won't work well ?!)
// perhaps it should be retried sometime...
function TDynamicIndex.StoreIndex( ParaIndex : integer ) : TDynamicIndex;
begin
mIndex := ParaIndex;
result.mIndex := mIndex;
result.mStride := mStride;
result.mDimensionCount := mDimensionCount;
result.mVolume := mVolume;
end;

class operator TDynamicIndex.Multiply( ParaA, ParaB : TDynamicIndex ) :
TDynamicIndex;
begin
result.mStride := 1;
result.mIndex := (ParaA.mIndex * ParaA.mStride) + (ParaB.mIndex *
ParaA.mVolume);
result.mVolume := (ParaA.mVolume * ParaB.mVolume);
end;

procedure Main;
var
X : TDynamicIndex;
Y : TDynamicIndex;
Z : TDynamicIndex;
Result : TDynamicIndex;
vErrorDetected : boolean;

vX : integer;
vY : integer;
vZ : integer;

vCheck : integer;
begin
X := TDynamicIndex.Create( 320, 1 );
Y := TDynamicIndex.Create( 200, 1 );
Z := TDynamicIndex.Create( 60, 1 );

// first a few single tests to see/show how it works.
Result := X[ 0 ] * Y[ 0 ] * Z[ 1 ]; // should display 320*200*1*1=64000
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 0 ] * Z[ 0 ]; // should display 319*1*1*1=319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100 ] * Z[ 0 ]; // should display 319*1 +
(100*320)*1*1 = 32319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100 ] * Z[ 5 ]; // should display 319*1 +
(100*320)*1 + (5*200*320)*1 = 32319 + 320000 = 352319
writeln( Result.mIndex );

// so far so could so now let's do some exhaustive/full verifications.
writeln('Verification started.');

vErrorDetected := false;
for vZ := 0 to 59 do
begin
for vY := 0 to 199 do
begin
for vX := 0 to 319 do
begin
Result := X[ vX ] * Y[ vY ] * Z[ vZ ];

vCheck := (vZ * 200 * 320) + (vY * 320) + vX;

if Result.mIndex <> vCheck then
begin
writeln('Index calculation error detected at (vX, vY, vZ): ' + '(' +
IntToStr(vX) + ',' + IntToStr(vY) + ',' + IntToStr(vZ) + ')' );
vErrorDetected := true;
end;
end;
end;
end;

writeln('Verification done.');

if vErrorDetected then
begin
writeln('Verification result: errors detected !');
end else
begin
writeln('Verification result: no errors detected.');
end;
end;

begin
try
Main;
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
end.

// *** End of Program ***

Bye,
Skybuck.

Skybuck Flying
Guest
Posts: n/a

 07-01-2011
I do consider this an important program at least for Delphi and perhaps
other languages.

I am not so sure about C++, perhaps C++ has other features which makes this
less interesting, then again it could still be interesting.

So I have converted the Delphi example to C++ example so C++ programmers can
have a looksy as well and enjoy it for what it's worth !

This code compiles and builds and runs properly in Visual Studio C++ 2010:

// *** Begin of Test Program ***
// TestProgram.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

struct TDynamicIndex
{
// private:
public:
int mIndex;
int mStride;
int mDimensionCount;
int mVolume;

public:

// default constructor
TDynamicIndex();

// custom constructor
TDynamicIndex( int ParaDimensionCount, int ParaStride );

// default destructor, not really needed by included for completeness
sake.
~TDynamicIndex();

// overloaded subscript operator, mimics delphi's indexed properties:
// intrigueing perhaps c++ can do references which delphi might not (or
perhaps c++ will be just as buggy, this can be explored/investigated
further/later),
// for now a value shall be returned to be consistent with delphi and
which was proven to work.
// TDynamicIndex & operator[] (const int ParaIndex);
TDynamicIndex operator[] (const int ParaIndex);

// overloaded multiply operator, mimics delphi's multiply operator
friend TDynamicIndex operator* (const TDynamicIndex &ParaA, const
TDynamicIndex &ParaB );
};

// default constructor
TDynamicIndex::TDynamicIndex()
{
mIndex = 0;
mStride = 1;
mDimensionCount = 1;
mVolume = 1;
}

// custom constructor
TDynamicIndex::TDynamicIndex( int ParaDimensionCount, int ParaStride )
{
mIndex = 0;
mStride = 1;
mDimensionCount = 1;
mVolume = 1;

{
}

if (ParaStride > 1)
{
mStride = ParaStride;
}

mVolume = mDimensionCount * mStride;
}

// default destructor
TDynamicIndex::~TDynamicIndex()
{

}

TDynamicIndex TDynamicIndex:perator[] (const int ParaIndex)
{
struct TDynamicIndex result;

mIndex = ParaIndex;
result.mIndex = mIndex;
result.mStride = mStride;
result.mDimensionCount = mDimensionCount;
result.mVolume = mVolume;

return result;
}

TDynamicIndex operator* (const TDynamicIndex &ParaA, const TDynamicIndex
&ParaB )
{
struct TDynamicIndex result;

result.mStride = 1;
result.mIndex = (ParaA.mIndex * ParaA.mStride) + (ParaB.mIndex *
ParaA.mVolume);
result.mVolume = (ParaA.mVolume * ParaB.mVolume);

return result;
}

int _tmain(int argc, _TCHAR* argv[])
{
TDynamicIndex X;
TDynamicIndex Y;
TDynamicIndex Z;
TDynamicIndex Result;
bool vErrorDetected;

int vX;
int vY;
int vZ;

int vCheck;

X = TDynamicIndex( 320, 1 );
Y = TDynamicIndex( 200, 1 );
Z = TDynamicIndex( 60, 1 );

// first a few single tests to see/show how it works.
Result = X[ 0 ] * Y[ 0 ] * Z[ 1 ]; // should display 320*200*1*1=64000
printf( "%d \n", Result.mIndex );

Result = X[ 319 ] * Y[ 0 ] * Z[ 0 ]; // should display 319*1*1*1=319
printf( "%d \n", Result.mIndex );

Result = X[ 319 ] * Y[ 100 ] * Z[ 0 ]; // should display 319*1 +
(100*320)*1*1 = 32319
printf( "%d \n", Result.mIndex );

Result = X[ 319 ] * Y[ 100 ] * Z[ 5 ]; // should display 319*1 + (100*320)*1
+ (5*200*320)*1 = 32319 + 320000 = 352319
printf( "%d \n", Result.mIndex );

// so far so good so now let's do some exhaustive/full verifications.
printf("Verification started.\n");

vErrorDetected = false;
for (vZ=0; vZ <= 59; vZ++)
{
for (vY=0; vY <= 199; vY++)
{
for (vX=0; vX <= 319; vX++)
{
Result = X[ vX ] * Y[ vY ] * Z[ vZ ];

vCheck = (vZ * 200 * 320) + (vY * 320) + vX;

if (Result.mIndex != vCheck)
{
printf("Index calculation error detected at (vX, vY, vZ): (%d, %d, %d)
\n", vX, vY, vZ );
vErrorDetected = true;
}
}
}
}

printf("Verification done.\n");

if (vErrorDetected == true)
{
printf("Verification result: errors detected !\n");
} else
{
printf("Verification result: no errors detected.\n");
};

return 0; // set a breakpoint here to pause the program and view the output.
}

// *** End of Test Program ***

Bye,

Skybuck.

Billy Mays
Guest
Posts: n/a

 07-01-2011
On 7/1/2011 12:18 AM, Skybuck Flying wrote:
> I do consider this an important program at least for Delphi and perhaps
> ...
>

Unless you have a question or a C program, please don't post to c.l.c

--
Bill

Skybuck Flying
Guest
Posts: n/a

 07-01-2011

"Billy Mays" wrote in message news:iujma5\$qkg\$(E-Mail Removed)...

On 7/1/2011 12:18 AM, Skybuck Flying wrote:
> I do consider this an important program at least for Delphi and perhaps
> ...
>

"
Unless you have a question or a C program, please don't post to c.l.c
"

I have a question for you:

Are there C compilers which were written in C++ ?

Bye,
Skybuck.

Skybuck Flying
Guest
Posts: n/a

 07-02-2011
Example updated for pointer support.

For pointer support an add-operator has been added, the idea is quite
simple:

x[ ... ] * y[ ... ] * z[...] + pointer := 100;

In practice because of left-side language limitations this has to be:

PSomeType( x[...] * y[...] * z[...] + pointer )^ := SomeType;

Furthermore my apperently favorite newsgroup has been added as well for a
total of 6 newsgroups which is 1 over the recommended ammount but worth
it for this posting

I shall leave original posting intact and only add the interface and
implementation code for this new feature, integrating this into the example
is left as an exercise for the reader and shouldn't be too difficult

TDynamicIndex = record
private
< ... snip... >
public
< ... snip... >
// *** NEW CODE ***:
class operator Add( ParaA : TDynamicIndex; ParaB : pointer ) : pointer;
end;

<... snip... <

// *** NEW CODE ***

class operator TDynamicIndex.Add( ParaA : TDynamicIndex; ParaB : pointer ) :
pointer;
begin
result := pointer( longword(ParaB) + longword(ParaA.mIndex) );
end;

Perhaps later I will convert this new code to C/C++ as well for now I am too
lazy for it and what to proceed with my Delphi code or so

But later I will probably need C/C++ code as well

// Original posting:

This is probably the most important test/demonstration program I ever wrote
and published/released onto the internet (up to this date (7 juli 2011)).

I hope compiler writers/programming language designers will study it
carefully and integrate it into their language.
(It's a bit long/lengthy read by well worth it ! Also casual programmers can
benefit from it as well !)

See comments for more details about the usefullness and the value of it for
present day and the future.

Also see test program way down below for usage example and verification
program.

Especially the formula's are very important.

"dynamic pointer indexing"

Which takes this step a bit further to provide direct memory access
(concept/thread which is still under development).

This posting takes a step back to evaluate and verify the formula's to be
used in "dynamic pointer indexing".

For now this example/concept can be thought of as "dynamic indexing".

Which can also be thought of as "multi-dimensional indexing".

A future which is currently missing in C/C++/CUDA C/C++ and in a way also
Delphi since Delphi requires a pointer array per additional dimension.

The technique illustrated below needs none of that Delphi overhead and
introduces it's own much smaller overhead, memory-wise, it does introduce a

There is also a hidden potential problem if parenthesis would be used.

A small explanation for the people that did not follow the other thread
mentioned:

The multiply operator is used as a passing mechanism to calculate a linear
index for the multi dimension indexes.

// *** Begin of Program ***

program TestProgram;

{\$APPTYPE CONSOLE}

{

Test dynamic multi dimensional index calculations

version 0.01 created on 1 juli 2011 by Skybuck Flying

To illustrate the theory behind dynamic multi dimension index calculations I
shall now
create a little test/demonstration program to show you how to write this
code and what
formula's to use.

The example deviates from the written theory so far in regard to the order,
the order
in the theory was assumed to be z, y, x however delphi's order appears to be
x, y, z.

Therefore the formula's will be adepted to Delphi's order.

For completeness sakes I shall mention the formula's in this comments one
more time.

How these formula's where derived I will not explain here because it was a
bit vague and messy but all in all not to bad.
But you don't need to know that... all that matters are the formula's you
can probably derive/come to the conclusion
how these were formed yourself and if not consider these a gift to you from
me !

Formula for index calculation in abstract form:

result.index =
(lower dimension parameter.index * lower dimension parameter.stride) +
(higher dimension parameter.index * lower dimension parameter.volume);

the resulting stride should be 1 until further notice
result.stride = 1;

Valueable notes for you to understand:

Strides always have a minimum of 1.
Volumes always have a minimum of 1.
DimensionCounts always have a minimum of 1.

These ones assure that none of the multiplications are zero-ed out, that
This is why these general formula's work. No matter if the stride is 1 and
the volume is 1 it will still work.
So some unnecessary multiplications with 1 might be done but so be it for
generalities sake.

The last formula you will need is the volume calculation in abstract form
which is actually quite simply:

result.volume = (lower dimension parameter.volume * higher dimension
parameter.volume);

It should be apperent to you now why this will work, but I shall explain it
anyway.

Since the order is from left to right which means low to high this will
work.

The lowest dimension is multiplied with the higher dimension giving a new
volume, in the first two dimension case
this would be the area (a volume with a depth of 1) the next dimension it is
multiplied with would give a new volume.
(a real 3d volume with a depth of depth). The next dimension it is
multiplied against gives a 4D volume. I use
the term "volume" for a lack of a better term for a 4D quanitity. So think
of a volume is that which describes
the entire (coordinate) space (or index space if you will).

I shall also give these two formula's in a somewhat more concrete and short
hand form for direct/easy/correct implementation purposes:

result.stride := 1;
result.index := (ParaA.Index * ParaA.Stride) + (ParaB.Index * ParaA.Volume);
result.volume := (ParaA.Volume * ParaB.Volume);

Now it's time for a test/demonstration program to proof to you that this is
not bullshit, to prove to you that is is valuable
and that this works and to show the power/flexibility of it so you will
hopefully see how usefull this would become
if this became a primary language feature with further support behind it !
=D

However the current code which shall be provided can already be of high
value for current day usasage ! =D

To show the usefullness of it a type will be introduced which shall
encompass this theory and these formula's.

This type shall be called "TDynamicIndex" it's purposes is many-fold:

To construct "dynamic" multi dimensional array indexing automatically.

So that the user programmer can easily adjust it's code to support all kinds
of 1D, 2D, 3D and xD dimensions.

Possibly layed out over a single dimension.

So this type calculates a linear index (which is the final/result index)
which can then be used to access for example
the memory system (which is a 1D entity).

Also to simply the design, the indexed property will be replaced with a
procedure, this illustrates
that the method is applieable to other languages which do not have
properties like c/c++, so this also illustrates
that the method works not because of properties but thanks to operator

However I have no way of setting the index value with indexed properties (a
procedure call would look ugly so I am going
to leave it in ! ) but rename it also a little bit to show what it does.

This test/demonstration program will also function as a verifier to verify
that the calculations are indeed correct.

Conclusion:

It works flawlessly so far.

This is probably one of the, if not the, most important test program and
theory I have ever published.

I hope compiler writers will study it carefully and will hopefully be able
to integrate this "technology" into
their programming languages so that we programmers can finally use "dynamic
pointers" and "dynamic indexes".. so
that we programmers can finally program easily in multiple dimensions which
translate to a linear/1d dimension for memory access.

So that we can finally have multi dimensional array indexing without
paying
penalties like additional pointers or difficult data
structure construction involving multiple array creations and such.

This demonstration and code will become more valuable as CUDA/OpenCL becomes
more valuable and widely used.

CUDA C/C++ is a perfect example of the
"multi dimensional indexing hell/linear index calculation hell, problem
distribution hell" that CUDA C/C++ programmers are now facing.

This code demonstration demonstrates how to solve it in a flexible way.

The usage example is hard coded to use the dimensions of x: 320 y: 200 z: 60
which represents the classic ms-dos vga
screen and a refresh rate of 60, (which was actually 70 at the time but ok),
so some programmers might be used to these dimensions
and might recgonize some of it.

Hopefully needless to say, this example is not limited to these dimensions,
and any dimension can be used.

A word of caution: integer has been used for volume. It's pretty easy to see
how the volume calculation might overflow
for large dimensions so keep an eye out of that. For now I shall let it be
an integer for speed's sake.

If an overflow occurs for your usage consider using an int64 for larger
dimension support.

This demonstration code has limited itself to indexes to keep things simple.

Strides have also been set to 1.

This represent a byte.

Changing the stride to 4 would represent an integer.

Only the first stride for the X dimension would need to be set to 4.

The other strides should be left alone and be set to 1.

Changing the stride would invalidate the verification program ofcourse.

Changing the code to automatically adept to changes should be obvious, but
for clearities sake
will not be done in version 0.01.

Perhaps version 0.02 might do this, but for now I see little value in it !

I shall now continue working on my TDynamicPointer concept which uses
the concepts presented here in TDynamicIndex and expands on it to support

}

uses
SysUtils;

type
TDynamicIndex = record
private
mIndex : integer;
mStride : integer;
mDimensionCount : integer;
mVolume : integer;

function StoreIndex( ParaIndex : integer ) : TDynamicIndex;
public
constructor Create( ParaDimensionCount : integer; ParaStride : integer );

property IndexOperator[ ParaIndex : integer ] : TDynamicIndex read
StoreIndex; default;

class operator Multiply( ParaA, ParaB : TDynamicIndex ) : TDynamicIndex;
end;

constructor TDynamicIndex.Create( ParaDimensionCount : integer; ParaStride :
integer );
begin
mIndex := 0;
mStride := 1;
mDimensionCount := 1;
mVolume := 1;

begin
end;

if ParaStride > 1 then
begin
mStride := ParaStride;
end;

mVolume := mDimensionCount * mStride;
end;

// store index, and return a copy, not because we want to, but because we
must
// I would much rather return a pointer, but unfortunately calling multiple
operator on pointer derefence won't work well ?!)
// perhaps it should be retried sometime...
function TDynamicIndex.StoreIndex( ParaIndex : integer ) : TDynamicIndex;
begin
mIndex := ParaIndex;
result.mIndex := mIndex;
result.mStride := mStride;
result.mDimensionCount := mDimensionCount;
result.mVolume := mVolume;
end;

class operator TDynamicIndex.Multiply( ParaA, ParaB : TDynamicIndex ) :
TDynamicIndex;
begin
result.mStride := 1;
result.mIndex := (ParaA.mIndex * ParaA.mStride) + (ParaB.mIndex *
ParaA.mVolume);
result.mVolume := (ParaA.mVolume * ParaB.mVolume);
end;

procedure Main;
var
X : TDynamicIndex;
Y : TDynamicIndex;
Z : TDynamicIndex;
Result : TDynamicIndex;
vErrorDetected : boolean;

vX : integer;
vY : integer;
vZ : integer;

vCheck : integer;
begin
X := TDynamicIndex.Create( 320, 1 );
Y := TDynamicIndex.Create( 200, 1 );
Z := TDynamicIndex.Create( 60, 1 );

// first a few single tests to see/show how it works.
Result := X[ 0 ] * Y[ 0 ] * Z[ 1 ]; // should display 320*200*1*1=64000
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 0 ] * Z[ 0 ]; // should display 319*1*1*1=319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100 ] * Z[ 0 ]; // should display 319*1 +
(100*320)*1*1 = 32319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100 ] * Z[ 5 ]; // should display 319*1 +
(100*320)*1 + (5*200*320)*1 = 32319 + 320000 = 352319
writeln( Result.mIndex );

// so far so could so now let's do some exhaustive/full verifications.
writeln('Verification started.');

vErrorDetected := false;
for vZ := 0 to 59 do
begin
for vY := 0 to 199 do
begin
for vX := 0 to 319 do
begin
Result := X[ vX ] * Y[ vY ] * Z[ vZ ];

vCheck := (vZ * 200 * 320) + (vY * 320) + vX;

if Result.mIndex <> vCheck then
begin
writeln('Index calculation error detected at (vX, vY, vZ): ' + '(' +
IntToStr(vX) + ',' + IntToStr(vY) + ',' + IntToStr(vZ) + ')' );
vErrorDetected := true;
end;
end;
end;
end;

writeln('Verification done.');

if vErrorDetected then
begin
writeln('Verification result: errors detected !');
end else
begin
writeln('Verification result: no errors detected.');
end;
end;

begin
try
Main;
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
end.

// *** End of Program ***

Bye,
Skybuck.

Skybuck Flying
Guest
Posts: n/a

 07-02-2011
Also for completeness sake I did add this line to the multiply operator to
provide a valid dimension count, this is also an interesting idea so that
multiplieing dimensions can also be tought of as creating one new single
dimension with a large count:

// not really needed for current code but let's do it anyway in case someone
or somebody or something might need it in the future
// at least this can give the user some kind of idea how many elements there
are in the multiplied dimension/plane/volume/etc.
// so that the record/variable/multiplication can also be considered a
lineair dimension which in itself is interesting too !
result.mDimensionCount := ParaA.mDimensionCount * ParaB.mDimensionCount;

Bye,
Skybuck.

Skybuck Flying
Guest
Posts: n/a

 07-02-2011
C/C++ example updated with pointer support and valid dimension count for
multiplied dimensions.

int used to typecasts pointers, could be changed to size_t or so.

(Example assumes 32 bit machine).

Idea is to use add-operator for pointer support as follows:

x[...] * y[...] * z[...] + pointer = 100;

// *** Begin of Test Program ***

// TestProgram.cpp : Defines the entry point for the console application.
//

// Test dynamic indexing (multi dimensional indexing)

// Converted from Delph to C++ on 1 juli 2011 by Skybuck Flying.

// version 0.01

// version 0.03 updated with pointer support and valid DimensionCount for
multiplied dimensions.

#include "stdafx.h"
#include "stdlib.h" // for malloc and free

struct TDynamicIndex
{
// private:
public:
int mIndex;
int mStride;
int mDimensionCount;
int mVolume;

public:

// default constructor
TDynamicIndex();

// custom constructor
TDynamicIndex( int ParaDimensionCount, int ParaStride );

// default destructor, not really needed but included for completeness
sake.
~TDynamicIndex();

// overloaded subscript operator, mimics delphi's indexed properties:
// intrigueing perhaps c++ can do references which delphi might not (or
perhaps c++ will be just as buggy, this can be explored/investigated
further/later),
// for now a value shall be returned to be consistent with delphi and
which was proven to work.
// TDynamicIndex & operator[] (const int ParaIndex);
TDynamicIndex operator[] (const int ParaIndex);

// overloaded multiply operator, mimics delphi's multiply operator
friend TDynamicIndex operator* (const TDynamicIndex &ParaA, const
TDynamicIndex &ParaB );

friend void* operator+ (const TDynamicIndex &ParaA, const void* ParaB );

};

// default constructor
TDynamicIndex::TDynamicIndex()
{
mIndex = 0;
mStride = 1;
mDimensionCount = 1;
mVolume = 1;
}

// custom constructor
TDynamicIndex::TDynamicIndex( int ParaDimensionCount, int ParaStride )
{
mIndex = 0;
mStride = 1;
mDimensionCount = 1;
mVolume = 1;

{
}

if (ParaStride > 1)
{
mStride = ParaStride;
}

mVolume = mDimensionCount * mStride;
}

// default destructor
TDynamicIndex::~TDynamicIndex()
{

}

TDynamicIndex TDynamicIndex:perator[] (const int ParaIndex)
{
struct TDynamicIndex result;

mIndex = ParaIndex;
result.mIndex = mIndex;
result.mStride = mStride;
result.mDimensionCount = mDimensionCount;
result.mVolume = mVolume;

return result;
}

TDynamicIndex operator* (const TDynamicIndex &ParaA, const TDynamicIndex
&ParaB )
{
struct TDynamicIndex result;

result.mStride = 1;
result.mIndex = (ParaA.mIndex * ParaA.mStride) + (ParaB.mIndex *
ParaA.mVolume);
result.mVolume = (ParaA.mVolume * ParaB.mVolume);
result.mDimensionCount = ParaA.mDimensionCount * ParaB.mDimensionCount;

return result;
}

void* operator+ (const TDynamicIndex &ParaA, const void* ParaB )
{
return ( (void *)( int(ParaB) + ParaA.mIndex ) );
}

int _tmain(int argc, _TCHAR* argv[])
{
void *Memory;

TDynamicIndex X;
TDynamicIndex Y;
TDynamicIndex Z;
TDynamicIndex Result;
bool vErrorDetected;

int vX;
int vY;
int vZ;

int vCheck;

Memory = malloc( 320 * 200 * 60 * 1 );

X = TDynamicIndex( 320, 1 );
Y = TDynamicIndex( 200, 1 );
Z = TDynamicIndex( 60, 1 );

// usage example for pointer functionality:
*((unsigned char*)( X[33] * Y[114] * Z[43] + Memory )) = 233;

vX = 33;
vY = 114;
vZ = 43;

vCheck = ( (vZ * 200 * 320) + (vY * 320) + vX ) * 1;

printf("%d \n", *((unsigned char *)( int(Memory) + vCheck )) ); // should
display 233

// first a few single tests to see/show how it works.
Result = X[ 0 ] * Y[ 0 ] * Z[ 1 ]; // should display 320*200*1*1=64000
printf( "%d \n", Result.mIndex );

Result = X[ 319 ] * Y[ 0 ] * Z[ 0 ]; // should display 319*1*1*1=319
printf( "%d \n", Result.mIndex );

Result = X[ 319 ] * Y[ 100 ] * Z[ 0 ]; // should display 319*1 +
(100*320)*1*1 = 32319
printf( "%d \n", Result.mIndex );

Result = X[ 319 ] * Y[ 100 ] * Z[ 5 ]; // should display 319*1 + (100*320)*1
+ (5*200*320)*1 = 32319 + 320000 = 352319
printf( "%d \n", Result.mIndex );

// so far so good so now let's do some exhaustive/full verifications.
printf("Verification started.\n");

vErrorDetected = false;
for (vZ=0; vZ <= 59; vZ++)
{
for (vY=0; vY <= 199; vY++)
{
for (vX=0; vX <= 319; vX++)
{
Result = X[ vX ] * Y[ vY ] * Z[ vZ ];

vCheck = (vZ * 200 * 320) + (vY * 320) + vX;

if (Result.mIndex != vCheck)
{
printf("Index calculation error detected at (vX, vY, vZ): (%d, %d, %d)
\n", vX, vY, vZ );
vErrorDetected = true;
}
}
}
}

printf("Verification done.\n");

if (vErrorDetected == true)
{
printf("Verification result: errors detected !\n");
} else
{
printf("Verification result: no errors detected.\n");
};

free( Memory );

return 0; // set a breakpoint here to pause the program and view the output.
}

// *** End of Test Program ***

Bye,

Skybuck.

Skybuck Flying
Guest
Posts: n/a

 07-02-2011
"
"

However I do not know how to configure Visual Studio 2010 to allow C only.

Furthermore it seems a bit a waste of time at least for me, perhaps not for
others which might be stuck using C compilers.

Here is a hint how it could be created, the function would look like:

output pointer FunctionName( input pointer, dimension structures, ... );

^ This function does the same as the multiply operator except it does it for
an entire array of parameters.

The parameters are then passed in in the following call:

FunctionName( Memory, X, 34, Y, 66, Z, 5 );

The numbers represents the indexes for x,y,z.

The x,y,z are the structures containing information like dimension size.

A create routine could be created which mimics the constructor:

CreateDynamicIndex( &X, 320, 1 ); // sets dimension and stride
CreateDynamicIndex( &Y, 200, 1 );
CreateDynamicIndex( &Z, 5, 1 );

The FunctionName could be named:

Pointer = MultiplyDynamicIndexes( Memory, X, 34, Y, 66, Z, 5 );

The rest should be obvious

Bye,
Skybuck.

Shao Miller
Guest
Posts: n/a

 07-02-2011
On 7/2/2011 12:21 AM, Skybuck Flying wrote:
> C/C++ example updated with pointer support and valid dimension count for
> multiplied dimensions.
>

Given that posters have suggested that "C/C++" is not really
appropriate, why do you continue to use it?

> #include "stdlib.h" // for malloc and free
> [...code...]
> struct TDynamicIndex
> {
> // private:
> public:
> int mIndex;
> int mStride;
> int mDimensionCount;
> int mVolume;
>
> public:
> [...code...]

This isn't C.