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]

On Thu, 10 Oct 2019 19:33:47 +0000, T. Ment wrote:

> 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]

On Thu, 10 Oct 2019 19:33:47 +0000, T. Ment wrote:

> 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]

On Sat, 18 Jul 2020 19:12:25 +0000, T. Ment wrote:

> 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:

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]

On Sat, 18 Jul 2020 19:12:25 +0000, T. Ment wrote:

> 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]

On Sat, 18 Jul 2020 19:12:25 +0000, T. Ment wrote:

> 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.

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]

On Sun, 19 Jul 2020 18:08:56 +0000, T. Ment wrote:

>> 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]

On 09.08.2020 17:51, T. Ment wrote:

> 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]

No link?

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

[wolfgang kern]

On 10.08.2020 13:28, T. Ment wrote:
> On Mon, 10 Aug 2020 08:15:47 +0200, wolfgang kern wrote:
>
>>> 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 ?

> 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]

On Tue, 11 Aug 2020 08:59:31 +0200, wolfgang kern wrote:

>>> 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.

>> 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]

On 11.08.2020 15:40, T. Ment wrote:
> On Tue, 11 Aug 2020 08:59:31 +0200, wolfgang kern wrote:
>
>>>> 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.

>>> 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]

On Wed, 12 Aug 2020 07:07:56 +0200, wolfgang kern wrote:

>> 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]

You mentioned "16 bytes"...

[T. Ment]

On Thu, 13 Aug 2020 04:16:21 +0200, wolfgang kern wrote:

>> 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]

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]

On Thu, 13 Aug 2020 09:00:13 +0200, wolfgang kern wrote:

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

>> Algorithm 3

> I looked at it

And still don't understand.

> 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.