Hello all, I am a new guy and this is my first post.

I am a reseracher in GIS/CS in Perth, West Oz and I work specifically with spatial data structures. I have been programming all my stuff in C (and later in C++) under both Unix and Windows. It occured to me that many of my algorithms dealt with bit manipulation which led me to thinking in terms of asm, which led me to this forum. An example of the type of stuff I am dealing with follows:

A linear quadtree (lqt) node of level 0 is a unit level pixel, level 1 = 2x2 pixels, level 2 = 4x4, etc. You can see then, that an lqt is a means by which to compress 2D images by accumulating homogeneous regions into square tiles. The structures that I have been developing explicitly insert edge information into these essentailly raster structures. Which means that I must account for this edge information when perfoming a boolean operation such as union or intersection on two images stored in my hybrid lqt format.

A traditional lqt node has this structure (with possible variations): colour | level stored as a two byte pair.

My idea was to modify this structure to encode edge information so I split the level byte into two 4 bit regions:

level | edge. The new structure now looks like this colour | (level | edge). As an example the binary rep of the NW corner of a BLACK region (which has both north and west bits set) and covers an 8x8 tile looks like this:

0000000100110011

where

00000001 = BLACK

0011 = level 3 (ie 4^3 = 8)

0011 = NW (in the scheme SENW)

If I have two input streams (2 edge encoded qts) I need to assess the edge patterns for valid aggregation. By this I mean, if 4 quadrants can be validly promoted to a higher level, that is, say four level 2 tiles into one level 3 tile, I must do so otherwise the output lqt would be sub-optimal.

To demonstrate a valid promotion (assume colour is the same):

Q1 Q2 Q3 Q4

level 2: 0011 0110 1001 1100 <--edge patterns

To demonstrate an invalid promotion (assume colour is the same):

Q1 Q2 Q3 Q4

level 2: 1111 0110 1001 1100 <--edge patterns

The algorithm I use is this:

if ( ( Q1( val ) ADD ( Q4 ( val ) ) AND ( ( Q2( val ) ADD ( Q3 ( val ) ) )

NodeAgg( Current node, Level++, edges = ( Q1( val ) ADD ( Q4 ( val ) )

else

Output( Q1, Q2, Q3, Q4 )

So in example 1 we have 15 = 15 so NodeAgg is called

but in example 2 we have 27 != 15 so the Output function is called.

I am new to asm programming and ask advice on how best to code this algorithm.

Thnx (and I apologise for being so windy)

rob

:)

I am a reseracher in GIS/CS in Perth, West Oz and I work specifically with spatial data structures. I have been programming all my stuff in C (and later in C++) under both Unix and Windows. It occured to me that many of my algorithms dealt with bit manipulation which led me to thinking in terms of asm, which led me to this forum. An example of the type of stuff I am dealing with follows:

A linear quadtree (lqt) node of level 0 is a unit level pixel, level 1 = 2x2 pixels, level 2 = 4x4, etc. You can see then, that an lqt is a means by which to compress 2D images by accumulating homogeneous regions into square tiles. The structures that I have been developing explicitly insert edge information into these essentailly raster structures. Which means that I must account for this edge information when perfoming a boolean operation such as union or intersection on two images stored in my hybrid lqt format.

A traditional lqt node has this structure (with possible variations): colour | level stored as a two byte pair.

My idea was to modify this structure to encode edge information so I split the level byte into two 4 bit regions:

level | edge. The new structure now looks like this colour | (level | edge). As an example the binary rep of the NW corner of a BLACK region (which has both north and west bits set) and covers an 8x8 tile looks like this:

0000000100110011

where

00000001 = BLACK

0011 = level 3 (ie 4^3 = 8)

0011 = NW (in the scheme SENW)

If I have two input streams (2 edge encoded qts) I need to assess the edge patterns for valid aggregation. By this I mean, if 4 quadrants can be validly promoted to a higher level, that is, say four level 2 tiles into one level 3 tile, I must do so otherwise the output lqt would be sub-optimal.

To demonstrate a valid promotion (assume colour is the same):

Q1 Q2 Q3 Q4

level 2: 0011 0110 1001 1100 <--edge patterns

To demonstrate an invalid promotion (assume colour is the same):

Q1 Q2 Q3 Q4

level 2: 1111 0110 1001 1100 <--edge patterns

The algorithm I use is this:

if ( ( Q1( val ) ADD ( Q4 ( val ) ) AND ( ( Q2( val ) ADD ( Q3 ( val ) ) )

NodeAgg( Current node, Level++, edges = ( Q1( val ) ADD ( Q4 ( val ) )

else

Output( Q1, Q2, Q3, Q4 )

So in example 1 we have 15 = 15 so NodeAgg is called

but in example 2 we have 27 != 15 so the Output function is called.

I am new to asm programming and ask advice on how best to code this algorithm.

Thnx (and I apologise for being so windy)

rob

:)

if ( ( Q1( val ) ADD ( Q4 ( val ) ) AND ( ( Q2( val ) ADD ( Q3 ( val ) ) )

I am presuming

Q1(val) == 0011b

Q2(val) == 0110b

Q3(val) == 1001b

Q4(val) == 1100b

Hence

Q1( val ) ADD ( Q4 ( val ) == 1111b

Q2( val ) ADD ( Q3 ( val ) == 1111b

1111b AND 1111b == 1111b -> This is non zero - hence true!

In the invalid case:

Q1(val) == 1111

Q2(val) == 0110

Q3(val) == 1001

Q4(val) == 1100

Q1( val ) ADD ( Q4 ( val ) == 11011b

Q2( val ) ADD ( Q3 ( val ) == 01111b

11011b AND 01111b = 1011b -> This is non zero - hence true!

They both follow the same code path? I thought that second case was invalid?

Is there is an additional case in the if for the overflow (ie A + B is greater than 4 bits long)?

Or am I missing something here?

Mirno

I am presuming

Q1(val) == 0011b

Q2(val) == 0110b

Q3(val) == 1001b

Q4(val) == 1100b

Hence

Q1( val ) ADD ( Q4 ( val ) == 1111b

Q2( val ) ADD ( Q3 ( val ) == 1111b

1111b AND 1111b == 1111b -> This is non zero - hence true!

In the invalid case:

Q1(val) == 1111

Q2(val) == 0110

Q3(val) == 1001

Q4(val) == 1100

Q1( val ) ADD ( Q4 ( val ) == 11011b

Q2( val ) ADD ( Q3 ( val ) == 01111b

11011b AND 01111b = 1011b -> This is non zero - hence true!

They both follow the same code path? I thought that second case was invalid?

Is there is an additional case in the if for the overflow (ie A + B is greater than 4 bits long)?

Or am I missing something here?

Mirno

**gisgeek**, I assume you mean == instead of AND, given your following statement.

```
if ( ( Q1( val ) ADD ( Q4 ( val ) ) [b]==[/b] ( ( Q2( val ) ADD ( Q3 ( val ) ) )
```

NodeAgg( Current node, Level++, edges = ( Q1( val ) ADD ( Q4 ( val ) )

else

Output( Q1, Q2, Q3, Q4 )

So in example 1 we have 15 = 15 so NodeAgg is called

but in example 2 we have 27 != 15 so the Output function is called.

It is hard to say much more than this:

```
mov eax, Q1.val
```

mov edx, Q2.val

add eax, Q4.val

add edx, Q3.val

cmp eax, edx

jne output

inc level

invoke current_node, level, edx

jmp continue

output:

invoke Output, Q1, Q2, Q3, Q4

continue:

Thank you both for taking the time,

And yes Mirno I mistakenly used AND where == was required. (which would handle the possible overflow that you pointed out)

Thanks bitRake for the solution. I'll try to make the next question more challenging.

cheers

rob

:alright:

And yes Mirno I mistakenly used AND where == was required. (which would handle the possible overflow that you pointed out)

Thanks bitRake for the solution. I'll try to make the next question more challenging.

cheers

rob

:alright:

Is this fractal compression you doing?

No, the compression isn't (necessarily) fractal, though there have been fractal methods applied to region quadtrees. The authors maintain that their solution provides "infinite" resolution but I suspect that this is a bit perpetual motion engine. Having said that, I admit that they have investigated and interesting line of work. Unfortunately the compression is lossy which is unsuitable for spatial science.

I am, however, investigating the Hausdorff fractal dimension as a tool to analyse spatial access methods based the regular decomposition of space such as Morton order (also known as Z ordering) (Faloutsos and Gaede: reference if you are interested). Also, there is value in fractal techniques as a complexity measure (ie shape analysis).

Cheers (windy again)

rob

I am, however, investigating the Hausdorff fractal dimension as a tool to analyse spatial access methods based the regular decomposition of space such as Morton order (also known as Z ordering) (Faloutsos and Gaede: reference if you are interested). Also, there is value in fractal techniques as a complexity measure (ie shape analysis).

Cheers (windy again)

rob

I've seen something similar used to generate octrees , mapping 3d space

in terms of three quadtrees, being the triaxial planes xz, xy,zy

I thought it was brilliant. Forget where I saw it though

:tongue: strange what sticks, aint it.

in terms of three quadtrees, being the triaxial planes xz, xy,zy

I thought it was brilliant. Forget where I saw it though

:tongue: strange what sticks, aint it.

I've seen wavelets do lossless compression,

wavelets dont work well on artificial type images, but would be perfect for image, terrain compression.

As far as i remember (never actually written any code for this - all theory :) for lossless you dont discard any of the co-efficients after the transform.

Quality is far better than jpeg at the same file size (for lossy compression)

wavelets dont work well on artificial type images, but would be perfect for image, terrain compression.

As far as i remember (never actually written any code for this - all theory :) for lossless you dont discard any of the co-efficients after the transform.

Quality is far better than jpeg at the same file size (for lossy compression)