Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.os.msdos.programmer > #3410 > unrolled thread

Block swapping

Back to article view | Back to comp.os.msdos.programmer

Contents

  Block swapping T. Ment <t.ment@protocol.invalid> - 2019-10-10 19:33 +0000
    Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2019-10-11 16:41 +0000
    Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-07-18 19:12 +0000
      Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-07-18 19:14 +0000
      Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-07-19 03:06 +0000
      Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-07-19 18:08 +0000
        Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-08-09 15:51 +0000
          Re: Block swapping wolfgang kern <nowhere@never.at> - 2020-08-10 08:15 +0200
            Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-08-10 11:28 +0000
              Re: Block swapping wolfgang kern <nowhere@never.at> - 2020-08-11 08:59 +0200
                Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-08-11 13:40 +0000
                  Re: Block swapping wolfgang kern <nowhere@never.at> - 2020-08-12 07:07 +0200
                    Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-08-12 12:49 +0000
                      Re: Block swapping wolfgang kern <nowhere@never.at> - 2020-08-13 04:16 +0200
                        Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-08-13 03:00 +0000
                          Re: Block swapping wolfgang kern <nowhere@never.at> - 2020-08-13 09:00 +0200
                            Re: Block swapping T. Ment <t.ment@protocol.invalid> - 2020-08-13 13:09 +0000

#3410 — Block swapping

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.

[toc] | [next] | [standalone]

#3418

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

[toc] | [prev] | [next] | [standalone]

#3888

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:

[toc] | [prev] | [next] | [standalone]

#3889

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

[toc] | [prev] | [next] | [standalone]

#3892

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

[toc] | [prev] | [next] | [standalone]

#3895

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

[toc] | [prev] | [next] | [standalone]

#3898

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.

[toc] | [prev] | [next] | [standalone]

#3899

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

[toc] | [prev] | [next] | [standalone]

#3900

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?

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

[toc] | [prev] | [next] | [standalone]

#3901

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

[toc] | [prev] | [next] | [standalone]

#3902

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.

[toc] | [prev] | [next] | [standalone]

#3903

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

[toc] | [prev] | [next] | [standalone]

#3904

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.

[toc] | [prev] | [next] | [standalone]

#3905

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

[toc] | [prev] | [next] | [standalone]

#3906

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.

[toc] | [prev] | [next] | [standalone]

#3907

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

[toc] | [prev] | [next] | [standalone]

#3908

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.os.msdos.programmer

csiph-web