• #### Block swapping

From T. Ment@21:1/5 to T. Ment on Sat Jul 18 19:12:25 2020
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:

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to T. Ment on Sat Jul 18 19:14:52 2020
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);
}

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to T. Ment on Sun Jul 19 03:06:32 2020
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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to T. Ment on Sun Jul 19 18:08:56 2020
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.

# 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);
}

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to T. Ment on Sun Aug 9 15:51:24 2020
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

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

Public folder, does not require registration.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From wolfgang kern@21:1/5 to T. Ment on Mon Aug 10 08:15:47 2020
On 09.08.2020 17:51, T. Ment wrote:

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

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to wolfgang kern on Mon Aug 10 11:28:48 2020
On Mon, 10 Aug 2020 08:15:47 +0200, wolfgang kern wrote:

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

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.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From wolfgang kern@21:1/5 to T. Ment on Tue Aug 11 08:59:31 2020
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.

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
necessary or automatic change direction to DOWN in case of overlapping.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to wolfgang kern on Tue Aug 11 13:40:42 2020
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.

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.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From wolfgang kern@21:1/5 to T. Ment on Wed Aug 12 07:07:56 2020
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.

where to ?

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to wolfgang kern on Wed Aug 12 12:49:05 2020
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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to wolfgang kern on Thu Aug 13 03:00:50 2020
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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From wolfgang kern@21:1/5 to T. Ment on Thu Aug 13 04:16:21 2020
On 12.08.2020 14:49, T. Ment wrote:
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.

You mentioned "16 bytes"...

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From wolfgang kern@21:1/5 to T. Ment on Thu Aug 13 09:00:13 2020
On 13.08.2020 05:00, T. Ment wrote:
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.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From T. Ment@21:1/5 to wolfgang kern on Thu Aug 13 13:09:43 2020
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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)