Block swapping

[T. Ment]

I'm reading DOS Internals chapter 6, resident programming in C. The
author uses a block swapping algorithm to exchange non resident code
with resident data. His explanation didn't make sense until I found
the same algorithm on the web.

http://kevingong.com/Math/BlockSwapping.html

(algorithm 3) The pictures helped me see what the code is all about.

Just some "news" I found interesting.

[T. Ment]

Post by T. Ment
I'm reading DOS Internals chapter 6, resident programming in C

Otherwise known as TSRs. The material gets deep, maybe more than needed
for most TSRs. Also, be advised the author is unapologetic that his code
requires Microsoft tools. Using other tools was not his goal, he relies
heavily on Microsoft features.

If you insist on using non-Microsoft tools, the book may frustrate more
than help.

It has too much code for me to type in, but the disk image solves that
problem. Only a savant could learn it without building and testing. And
for that you need Microsoft tools.

The book source code is available on Vetusware (DOS_Internals.zip) and
the author has errata on his website.

https://www.geoffchappell.com/notes/dos/internals/index.htm

[T. Ment]

Post by T. Ment
I'm reading DOS Internals chapter 6, resident programming in C. The
author uses a block swapping algorithm to exchange non resident code
with resident data. His explanation didn't make sense until I found
the same algorithm on the web.
http://kevingong.com/Math/BlockSwapping.html
(algorithm 3) The pictures helped me see what the code is all about.

Though the pictures help, I still couldn't understand how it works. As
Kevin Gong says:

There's a fairly straightforward method which is the most efficient
(but hardest to program and somewhat difficult to analyze)

So I started coding some output to see what's going on. After much trial
and error, I finally got it. Here's the code:

[T. Ment]

Post by T. Ment
So I started coding some output to see what's going on. After much trial

Whoops no attachment, hit the wrong button. Try again:



# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <conio.h>

char *data;
int new, old; /* position */
int count, cycle;
int lsize, rsize, size;

void
show (void)
{
int x;

for (x = 0; x < size; x++) {
printf (" %c ", data[x]);
}

printf ("\n");

for (x = 0; x < size; x++) {
if (x == new)
printf (" %2d+", x);
else if (x == old)
printf (" %2d-", x);
else
printf (" ", x);
}

printf (" %2d %2d\n\n", cycle, count);
}

void
main (int argc, char **argv)
{
if (argc != 3) {
bogus:
printf ("bogus input\n");
exit (1);
}

lsize = strlen (argv[1]);
rsize = strlen (argv[2]);
size = lsize + rsize;
if (size > 16)
goto bogus;

data = calloc (size + 1, 1);
strcpy (data, argv[1]);
strcpy (data + lsize, argv[2]);

clrscr ();

count = size;
cycle = 0;

while (count) {
new = cycle;
data[size] = data[new]; /* use extra space to begin cycle */

for (;;) {
if (new < rsize) /* demarcates final blocks */
old = new + lsize; /* right moves left by left size */
else
old = new - rsize; /* left moves right by right size */

if (old == cycle) /* end of cycle */
break;

data[new] = data[old]; /* copy to new position */
data[old] = ' '; /* erase old */
show ();

new = old; /* erased old becomes next new */

--count;
}

data[new] = data[size]; /* use extra space to close cycle */
show ();

if (--count) /* not done yet, start next cycle */
++cycle;
}

exit (0);
}

[T. Ment]

Post by T. Ment
So I started coding some output to see what's going on.

Sample output:


bswap taste good


g a s t e o o d
0+ 5- 0 9

g s t e a o o d
1- 5+ 0 8

g o s t e a o d
1+ 6- 0 7

g o t e a s o d
2- 6+ 0 6

g o o t e a s d
2+ 7- 0 5

g o o e a s t d
3- 7+ 0 4

g o o d e a s t
3+ 8- 0 3

g o o d a s t e
4- 8+ 0 2

g o o d t a s t e
0- 4+ 0 1

[T. Ment]

Post by T. Ment
Here's the code

With comments clarified and code optimized. It's not hard when you have
working code to look at. I wonder who discovered the algorithm. It's not
easy starting from scratch.


# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <conio.h>

char *data;
int new, old; /* position */
int count, cycle;
int lsize, rsize, size;

void
show (void)
{
int x;

for (x = 0; x < size; x++) {
printf (" %c ", data[x]);
}

printf ("\n");

for (x = 0; x < size; x++) {
if (x == new)
printf (" %2d+", x);
else if (x == old)
printf (" %2d-", x);
else
printf (" ", x);
}

printf (" %2d %2d\n\n", cycle, count);
}

void
main (int argc, char **argv)
{
if (argc != 3) {
bogus:
printf ("bogus input\n");
exit (1);
}

lsize = strlen (argv[1]);
rsize = strlen (argv[2]);
size = lsize + rsize;
if (size > 16)
goto bogus;

data = calloc (size + 1, 1);
strcpy (data, argv[1]);
strcpy (data + lsize, argv[2]);

clrscr ();

count = size;
cycle = 0;

for (;;) {
new = cycle;
data[size] = data[new]; /* use extra space to begin cycle */

for (;;) {
--count; /* know when done */

if (new < rsize) /* border of final blocks */
old = new + lsize; /* right moves left by left size */
else
old = new - rsize; /* left moves right by right size */

if (old == cycle) /* end of cycle */
break;

data[new] = data[old]; /* copy to new position */
data[old] = ' '; /* erase old */
show ();

new = old; /* erased old becomes next new */
}

data[new] = data[size]; /* use extra space to close cycle */
show ();

if (count) /* not done yet */
++cycle; /* need another cycle */
else
break;
}

exit (0);
}

[T. Ment]

Post by T. Ment

Post by T. Ment
Here's the code

With comments clarified and code optimized. It's not hard when you have
working code to look at. I wonder who discovered the algorithm.

Writing C code helped me understand the algorithm.

Then I rewrote my C code in asm, and compared it to Chappell's, I used
extra variables which made it easier to understand. Because of that, my
code was longer and not as efficient.

Then I read Chappell's code again. It's tightly optimized, and not easy
to understand. I still didn't get it. I looked for flowcharting software
and settled on google draw. Amazing what they can do with javascript in
a web browser. I downloaded the flowchart as a PDF and uploaded that to
dropbox.

With the flowchart, I see what Chappell's code is doing.

https://www.dropbox.com/sh/552uvzndigyv1ym/AADoUObtPej33fZk1SN3lNhKa?dl=0

Public folder, does not require registration.

[wolfgang kern]

Post by T. Ment
With the flowchart, I see what Chappell's code is doing.
https://www.dropbox.com/sh/552uvzndigyv1ym/AADoUObtPej33fZk1SN3lNhKa?dl=0
Public folder, does not require registration.

it's OK for pure DOS. my block-move/-swap/-merge routines are much
simpler because I use BIG-REALmode and can work on linear addresses with
only little overhead to calculate seg:offs-->LINADR and swap Dest/Src if
necessary or automatic change direction to DOWN in case of overlapping.
__
wolfgang

[T. Ment]

Post by wolfgang kern

Post by T. Ment
With the flowchart, I see what Chappell's code is doing.
https://www.dropbox.com/sh/552uvzndigyv1ym/AADoUObtPej33fZk1SN3lNhKa?dl=0
Public folder, does not require registration.

it's OK for pure DOS. my block-move/-swap/-merge routines are much
simpler because I use BIG-REALmode and can work on linear addresses with
only little overhead to calculate seg:offs-->LINADR and swap Dest/Src if
necessary or automatic change direction to DOWN in case of overlapping.

No link?

Chappell's code swaps blocks using minimal extra space (16 bytes). Can
you beat that?

[wolfgang kern]

Post by T. Ment

Post by wolfgang kern

Post by T. Ment
With the flowchart, I see what Chappell's code is doing.
https://www.dropbox.com/sh/552uvzndigyv1ym/AADoUObtPej33fZk1SN3lNhKa?dl=0
Public folder, does not require registration.

it's OK for pure DOS. my block-move/-swap/-merge routines are much
simpler because I use BIG-REALmode and can work on linear addresses with
only little overhead to calculate seg:offs-->LINADR and swap Dest/Src if
necessary or automatic change direction to DOWN in case of overlapping.

No link?

where to ?

Post by T. Ment
Chappell's code swaps blocks using minimal extra space (16 bytes). Can
you beat that?

I'd like to see this 16 bytes in hex before any attempt to shrink it.
__
wolfgang

[T. Ment]

Post by wolfgang kern

Post by T. Ment

Post by wolfgang kern
it's OK for pure DOS. my block-move/-swap/-merge routines are much
simpler because I use BIG-REALmode and can work on linear addresses with
only little overhead to calculate seg:offs-->LINADR and swap Dest/Src if
necessary or automatic change direction to DOWN in case of overlapping.

No link?

where to ?

Your purported magnificent code.

Post by wolfgang kern

Post by T. Ment
Chappell's code swaps blocks using minimal extra space (16 bytes). Can
you beat that?

I'd like to see this 16 bytes in hex before any attempt to shrink it.

You have the wrong idea. Chappell's book explains if you care to know.

[wolfgang kern]

Post by T. Ment

Post by wolfgang kern

Post by T. Ment

Post by wolfgang kern
it's OK for pure DOS. my block-move/-swap/-merge routines are much
simpler because I use BIG-REALmode and can work on linear addresses with
only little overhead to calculate seg:offs-->LINADR and swap Dest/Src if
necessary or automatic change direction to DOWN in case of overlapping.

No link?

where to ?

Your purported magnificent code.

it was part of my old DOS-extender, now all is in my OS un-Protected
32/64 bit FLAT, but the code remained almost the same.
Sorry there are no code-snips available, It would need me to manual
enter ASM-lines here.

Post by T. Ment

Post by wolfgang kern

Post by T. Ment
Chappell's code swaps blocks using minimal extra space (16 bytes). Can
you beat that?

I'd like to see this 16 bytes in hex before any attempt to shrink it.

You have the wrong idea. Chappell's book explains if you care to know.

I haven't seen any hex-dump nor an assembly for it
__
wolfgang

[T. Ment]

Post by wolfgang kern

Post by T. Ment
You have the wrong idea. Chappell's book explains if you care to know.

I haven't seen any hex-dump nor an assembly for it

IDK what you're talking about, but it's not what I'm talking about.

[wolfgang kern]

Post by T. Ment

Post by wolfgang kern

Post by T. Ment
You have the wrong idea. Chappell's book explains if you care to know.

I haven't seen any hex-dump nor an assembly for it

IDK what you're talking about, but it's not what I'm talking about.

You mentioned "16 bytes"...

[T. Ment]

Post by wolfgang kern

Post by T. Ment
IDK what you're talking about, but it's not what I'm talking about.

You mentioned "16 bytes"...

Chappell's unit size is 16 bytes. But the algorithm works with any unit
size.

http://kevingong.com/Math/BlockSwapping.html

Algorithm 3

If you jumped into the middle of this thread and thought it was about
something else, or want to talk about something else, you can stop now.

[wolfgang kern]

Post by T. Ment

Post by wolfgang kern

Post by T. Ment
IDK what you're talking about, but it's not what I'm talking about.

You mentioned "16 bytes"...

Chappell's unit size is 16 bytes. But the algorithm works with any unit
size.
http://kevingong.com/Math/BlockSwapping.html
Algorithm 3
If you jumped into the middle of this thread and thought it was about
something else, or want to talk about something else, you can stop now.

OMG, I looked at it and why use easy words when it can be expressed as
complicated as possible ? :)

swap: :assume cx holds size
mov AL,[S_1]
xchg AL,[S_2]
mov [S_1],AL
inc S_1
inc S_2
loop swap

[T. Ment]

Post by wolfgang kern

Post by T. Ment
http://kevingong.com/Math/BlockSwapping.html
Algorithm 3

I looked at it

And still don't understand.

Post by wolfgang kern
swap: :assume cx holds size
mov AL,[S_1]
xchg AL,[S_2]
mov [S_1],AL
inc S_1
inc S_2
loop swap

Nope. You failed the interview.