Jump to content

Photo

Need a readout on an algorithm in The Learning phone (PLATO)


17 replies to this topic

#1 tschak909 OFFLINE  

tschak909

    River Patroller

  • 2,783 posts
  • Location:USA

Posted Mon Jun 11, 2018 4:42 PM

I am smack dab in the middle of implementing a new PLATO terminal for all 8-bit machines (including the Atari), and I'm trying to see how the font-resizing is done on the fly from the original 8 16-bit words (8x16) font to the target size of (5x6), so that I can reimplement it in C.

 

PLATO terminals can, and do download fonts from the central system, they receive them as a series of memory write commands that write into the character set memory. The PLATO cartridge has routines which translate these addresses (0x3800) into relative offsets (0x0000, 0x0001, etc.) and I understand how that works... what I'm curious about, is that the PLATO cartridge seems to be doing image processing to squeeze the character set bitmaps down to fit in the allotted space as the download occurs. How is this happening?

 

Relevant code is here: https://github.com/j...r/tlp.asm#L2589

 

-Thom



#2 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Mon Jun 11, 2018 5:06 PM

For cross reference, here is an earlier, but original source code listing for the Atari PLATO cart: https://paste.ubuntu.com/p/pnpkxDxc54/



#3 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Tue Jun 12, 2018 11:45 AM

As luck would have it, 16kram has been reading through this routine as part of figuring out why character set corruption happens everywhere else except Altirra, and has documented the whole routine. This thing is insane!

 

https://github.com/m...3/tlp.asm#L2620

 

-Thom



#4 Rybags ONLINE  

Rybags

    Quadrunner

  • 15,793 posts
  • Location:Australia

Posted Tue Jun 12, 2018 7:41 PM

Have to wonder how such a transform looks, it's a pretty big reduction.

 

I was thinking about a similar approach for doing a Star Wars type scroller - the problem there being that the number of tables needed could potentially be huge.



#5 phaeron OFFLINE  

phaeron

    River Patroller

  • 2,584 posts
  • Location:USA

Posted Tue Jun 12, 2018 9:38 PM

This mainly looks like box filtering + thresholding. Probably could be tightened up quite a bit as there's a bunch of X/Y addressing that looks unnecessary.



#6 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Wed Jun 13, 2018 9:24 AM

Have to wonder how such a transform looks, it's a pretty big reduction.

 

I was thinking about a similar approach for doing a Star Wars type scroller - the problem there being that the number of tables needed could potentially be huge.

 

It actually works, you should try the PLATO cartridge sometime. Come over to my website.

 

-Thom



#7 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Thu Jul 19, 2018 10:52 PM

can I convince somebody to take a whack at turning this into C? I've been attempting to visualize the algorithm in my head enough to do so and my head is seizing up.. :( could be my life's external stress, though... this is the LAST major piece that I need to implement so that PLATOTerm can be finished...

 

(this is another way of saying, help, I suck at this type of algorithm work) :(

 

-Thom


Edited by tschak909, Thu Jul 19, 2018 10:53 PM.


#8 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Thu Jul 26, 2018 6:21 PM

So far, have gotten the pixel transposition working, and algorithm A is working:

 

transpose:

  // Transpose character data.
  for (curr_word=0;curr_word<8;curr_word++)
    {
      temp_word=word_data[curr_word];
      for (u=16; u-->0; )
        {
          if (temp_word & 1<<u)
            {
              pix_cnt++;
              PIX_WEIGHTS[TAB_0_25[TAB_0_5[u]]+TAB_0_4[curr_word]]++;
              char_data[u]|=BTAB[curr_word];
            }
        }
    }

  printf("pix_cnt %d\n",pix_cnt);

Algorithm A:

  if (pix_cnt <= 54 || pix_cnt < 85)
    {
      // Algorithm A - approx Half of pixels are set
      printf("using algorithm A\n\n");
      for (v=6; v-->0; )
        {
          for (w=5; w-->0; )
            {
              if (PIX_WEIGHTS[TAB_0_25[v]+w] >= PIX_THRESH[TAB_0_25[v]+w])
                shrunk_char_data[v]|=BTAB[w];
            }
        }
    }

Algorithm A is used when approximately half of the 128 possible pixels in the original bitmap are filled.

 

Algorithm B is used for everything else, either sparsely populated bitmaps, or densely populated ones...

 

but I'm getting thrown for a loop because the Y index is being rewritten...am trying to not just blindly copy the algorithm, but understand what's going on, and why...

 

(any insight anyone could give would be helpful...)

 

-Thom



#9 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Thu Jul 26, 2018 9:29 PM

I tried a first pass at algorithm B and tried to hook it up to the terminal code, with the following code:

/**
 * PLATOTerm64 - A PLATO Terminal for the Commodore 64
 * Based on Steve Peltz's PAD
 * 
 * Author: Thomas Cherryhomes <thom.cherryhomes at gmail dot com>
 *
 * terminal_char_load.c - Character set loading routine for 5x6 font.
 */

#include <string.h>
#include "../terminal.h"
#include "../protocol.h"

// Temporary PLATO character data, 8x16 matrix
static unsigned char char_data[]={0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
				  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};

static unsigned char MTAB[]={0x7F,0xBf,0xDF,0xEF,0xF7,0xFB,0xFD,0xFE}; // flip one bit off (AND)
static unsigned char BTAB[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01}; // flip one bit on (OR)
static unsigned char BTAB_5[]={0x08,0x10,0x10,0x20,0x20,0x40,0x80,0x80}; // flip one bit on for the 5x6 matrix (OR)

static unsigned char TAB_0_5[]={0x00,0x00,0x00,0x01,0x01,0x01,0x02,0x02,
				0x03,0x03,0x04,0x04,0x04,0x05,0x05,0x05}; // return 0..5 given index 0 to 15.

static unsigned char TAB_0_4[]={0x00,0x00,0x01,0x02,0x02,0x03,0x03,0x04}; // return 0..4 given index 0 to 7

static unsigned char PIX_THRESH[]={0x03,0x02,0x03,0x03,0x02, // Pixel threshold table.
				   0x03,0x02,0x03,0x03,0x02,
				   0x02,0x01,0x02,0x02,0x01,
				   0x02,0x01,0x02,0x02,0x01,
				   0x03,0x02,0x03,0x03,0x02,
				   0x03,0x02,0x03,0x03,0x02};

static unsigned char PIX_WEIGHTS[]={0x00,0x00,0x00,0x00,0x00, // Pixel weights
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00};

static unsigned char TAB_0_25[]={0,5,10,15,20,25}; // Given index 0 of 5, return multiple of 5.

static unsigned char pix_cnt;     // total # of pixels
static unsigned char curr_word;   // current word
static unsigned char u,v,w;       // loop counters

extern unsigned char fontm23[768];
extern unsigned short fontptr[160];

/**
 * terminal_char_load - Store a character into the user definable
 * character set.
 */
void terminal_char_load(padWord charnum, charData theChar)
{
  // Transpose character data.
  for (curr_word=0;curr_word<8;curr_word++)
    {
      for (u=16; u-->0; )
	{
	  if (theChar[curr_word] & 1<<u)
	    {
	      pix_cnt++;
	      PIX_WEIGHTS[TAB_0_25[TAB_0_5[u]]+TAB_0_4[curr_word]]++;
	      char_data[u]|=BTAB[curr_word];
	    }
	}
    }

  // Determine algorithm to use for number of pixels.
  // Algorithm A is used when roughly half of the # of pixels are set.
  // Algorithm B is used either when the image is densely or sparsely populated (based on pix_cnt).
  if ((pix_cnt <= 54) && (pix_cnt < 85))
    {
      // Algorithm A - approx Half of pixels are set
      for (v=6; v-->0; )
  	{
  	  for (w=5; w-->0; )
  	    {
  	      if (PIX_WEIGHTS[TAB_0_25[v]+w] >= PIX_THRESH[TAB_0_25[v]+w])
  		fontm23[fontptr[charnum]+v]|=BTAB[w];
  	    }
  	}
    }
  else if ((pix_cnt < 54) || (pix_cnt >= 85))
    {
      // Algorithm B - Sparsely or heavily populated bitmaps
      for (v=16; v-->0; )
	{
	  for (w=8; w-->0; )
	    {
	      if (char_data[v] & (1<<w))
		{
		  fontm23[fontptr[charnum]+v]|=BTAB_5[w];
		}
	    }
	}
    }
  
}

Tried in my test harness and got:

 

pix_cnt 66
using algorithm A
 
11111100
11111100
01111110
01111110
00111111
00111111
00011111
00011111
00001111
00001111
00000111
00000111
00000011
00000011
00000001
00000001
-----------
|5|3|6|4|0|
|1|3|6|6|2|
|0|0|4|4|2|
|0|0|2|4|2|
|0|0|0|5|3|
|0|0|0|1|3|
-----------
 
 
11110000
01111000
00111000
00111000
00011000
00001000
 
 
but terminal output gives me:
korcyHH.png
 
shit.
 
-Thom


#10 _The Doctor__ OFFLINE  

_The Doctor__

    Quadrunner

  • 5,224 posts
  • Location:10-0-11-00:02

Posted Thu Jul 26, 2018 9:46 PM

At first I thought you were concentrating on getting the Atari 8 bit version improved and breaking it free of some embedded serial issues, but it seems as if your kind of doing a little of this a little of that and work harder on getting this to other platforms.... in all honesty you might have better luck going after the Apple 2 as a target port... it just seems to work out better tackling a move in that direction and then swinging round to the c64.... If you can keep it all straight- that in itself would be amazing... so many directions at once...

 

  I know you want it all and I hope you find the right people to help out. I really think you need some mathematicians to help you out, more so than some of us code monkeys. My suggestion is to ask some colleges that focus on these areas to give it a go... you will get a handful of choices and some better insight from those that are immersed in it, I'm sure a prof or two would find such things fun as well.

 

all that being said it's still nice to follow along and get some thoughts and a look at what you are up to.


Edited by _The Doctor__, Thu Jul 26, 2018 9:47 PM.


#11 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Thu Jul 26, 2018 9:55 PM

*takes-a-deep-breath* (tries not to get irritated, please give me some latitude as I have been churning through THIS ONE ALGORITHM for weeks, now, while also porting this to 12 platforms AT THE SAME TIME.)

 

I've been porting this to multiple platforms, using the same core C code, this has been, for the most part, successful. The LAST part of the functionality that I needed, was LITERALLY the custom character set loading/scaling, which I am tackling, now.

 

It works on the Apple II:

 

IHWSXrd.png

 

It works on the Commodore 64:

00PaE26.jpg

 

It works on the Commodore 128 with 64k of VDC ram to provide a 512x512 interlaced full PLATO screen:

KRQeocr.jpg

 

There is a preliminary bring-up on the Atari, but the serial driver needs to be relocated:

ZNXW43X.png

 

and more are coming...all from the same C code, all being built for every damned 8-bit and 16-bit system that I can construct a toolchain for.

 

I do appreciate the advice, but I've got a mission here, and I am getting shit done, I am asking for help so that it can be done SOONER, rather than LATER, and at this point need far more productive answers.

 

-Thom



#12 _The Doctor__ OFFLINE  

_The Doctor__

    Quadrunner

  • 5,224 posts
  • Location:10-0-11-00:02

Posted Thu Jul 26, 2018 10:50 PM

getting quick help from some mathematicians at some colleges to get it done was not going to be productive?... they're way smarter at algorithms, encrypting, decryption, a whole multitude of other things.

-  Yes working on everything except that last one... got it.    and since I saw no answers posted for your current conundrum I thought it helpful to direct you to a group or crew of folks who live for this sort of thing. Sorry to have irritated you... I am certain you would have known everything there was to know and was in the learning phone without any nudges.

 

I actually had some one interested in helping you from Lafayette College (his name is Michael), after he read your post he basically walked away... good job!

 

I'm taken aback and don't know what to say, other than best wishes and good luck.


Edited by _The Doctor__, Thu Jul 26, 2018 11:02 PM.


#13 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Thu Jul 26, 2018 11:02 PM

Now you're just being full of it. Seriously, don't say "I was gonna give some help but you said something I didn't like, so NYAH!" ... I smell stuff like this from people, and I call it out, reflexively.

If you had ACTUALLY READ the initial source code I posted, you'd see that I DO _NOT_ need a mathematician to make sense of this. I needed a read-out of the algorithm. It's fine, I got along without it, but I was trying to get some help, so that I didn't need to spend two and a half weeks churning through it on paper, to understand what was going on.

 

As I said, I have multiple speaking engagements, am doing (QUITE SUCCESSFULLY) multiple ports of the software (FROM THE SAME CODEBASE), and am having to slice my time ultra thin to pull this all off. All of the things a mathematician would be needed for, have already been done, in the algorithm description...

 

even Avery was able to indicate the nature of the algorithm, which actually helped a great deal, as it gave me a direction to do a ton of research into the backgrounds of how such algorithms worked... turned out that the algorithm presented here is highly simplified from what is usually presented in most examples on the subject.

 

what you're saying, made zero sense.

 

-Thom


Edited by tschak909, Thu Jul 26, 2018 11:12 PM.


#14 _The Doctor__ OFFLINE  

_The Doctor__

    Quadrunner

  • 5,224 posts
  • Location:10-0-11-00:02

Posted Thu Jul 26, 2018 11:22 PM

If I knew this was all about you pounding your chest and letting everyone know how wonderful and successful you are I wouldn't have bothered at all sorry again... your right I didn't read everything you posted and to be honest part way through your last post I just skipped to make this reply.  I am certain you didn't need any of us really..... I think you have everything and everyone you need. Judging by what little I have read and you last partially read post you didn't need anything at all...    your just thinking out loud...  such a tolerant and understanding individual such as yourself should be able to forgive these transgressions.....

 

so you needed some one to skim through it and tell you what they thought it was doing, resembled, or looked like.... okay, avery did that.

 

but you also posted that it wasn't as expected... followed by the ever colorful expletive 'sh*t'

 

and since you are frustrated at the failed output, feel free to take it out on me....  I thought you needed help, and I took it upon myself to find someone to help you with the math and code...   since he clearly isn't interested in helping you now. And I had the pleasure of  your impassioned response, I can only apologize for over stepping some bounds I clearly was unaware of. NO ONE WAS TRYING TO STEAL YOUR THUNDER!

 

Good day,

_The Door Mat__


Edited by _The Doctor__, Thu Jul 26, 2018 11:36 PM.


#15 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Sat Jul 28, 2018 3:28 PM

Looks like I'm almost there. So far, just an edge case that's not quite right.

 

Given the following code:

/**
 * PLATOTerm64 - A PLATO Terminal for the Commodore 64
 * Based on Steve Peltz's PAD
 * 
 * Author: Thomas Cherryhomes <thom.cherryhomes at gmail dot com>
 *
 * terminal_char_load.c - Character set loading routine for 5x6 font.
 */

#include <cbm.h>
#include <c64.h>
#include <string.h>
#include <stdio.h>
#include <stdarg.h>
#include "../terminal.h"
#include "../protocol.h"

// Temporary PLATO character data, 8x16 matrix
static unsigned char char_data[]={0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
				  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};

static unsigned char BTAB[]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01}; // flip one bit on (OR)
static unsigned char BTAB_5[]={0x08,0x10,0x10,0x20,0x20,0x40,0x80,0x80}; // flip one bit on for the 5x6 matrix (OR)

static unsigned char TAB_0_5[]={0x05,0x05,0x05,0x04,0x04,0x04,0x03,0x03,0x02,0x02,0x01,0x01,0x01,0x00,0x00,0x00};
static unsigned char TAB_0_5i[]={0x00,0x00,0x00,0x01,0x01,0x01,0x02,0x02,0x03,0x03,0x04,0x04,0x04,0x05,0x05,0x05};

static unsigned char TAB_0_4[]={0x00,0x00,0x01,0x02,0x02,0x03,0x03,0x04}; // return 0..4 given index 0 to 7

static unsigned char PIX_THRESH[]={0x03,0x02,0x03,0x03,0x02, // Pixel threshold table.
				   0x03,0x02,0x03,0x03,0x02,
				   0x02,0x01,0x02,0x02,0x01,
				   0x02,0x01,0x02,0x02,0x01,
				   0x03,0x02,0x03,0x03,0x02,
				   0x03,0x02,0x03,0x03,0x02};

static unsigned char PIX_WEIGHTS[]={0x00,0x00,0x00,0x00,0x00, // Pixel weights
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00,
				    0x00,0x00,0x00,0x00,0x00};

static unsigned char TAB_0_25[]={0,5,10,15,20,25}; // Given index 0 of 5, return multiple of 5.

static unsigned char pix_cnt;     // total # of pixels
static unsigned char curr_word;   // current word
static unsigned char u,v;       // loop counters

extern unsigned char fontm23[768];
extern unsigned short fontptr[160];

/**
 * terminal_char_load - Store a character into the user definable
 * character set.
 */
void terminal_char_load(padWord charnum, charData theChar)
{
  // Clear char data. 
  memset(char_data,0,sizeof(char_data));
  memset(PIX_WEIGHTS,0,sizeof(PIX_WEIGHTS));
  memset(&fontm23[fontptr[charnum]],0,6);
  
  // Transpose character data.  
  for (curr_word=0;curr_word<8;curr_word++)
    {
      for (u=16; u-->0; )
	{
	  if (theChar[curr_word] & 1<<u)
	    {
	      pix_cnt++;
	      PIX_WEIGHTS[TAB_0_25[TAB_0_5[u]]+TAB_0_4[curr_word]]++;
	      char_data[u^0x0F&0x0F]|=BTAB[curr_word];
	    }
	}
    }

  // Determine algorithm to use for number of pixels.
  // Algorithm A is used when roughly half of the # of pixels are set.
  // Algorithm B is used either when the image is densely or sparsely populated (based on pix_cnt).
  if ((54 <= pix_cnt) && (pix_cnt < 85))
    {
      // Algorithm A - approx Half of pixels are set
      for (u=6; u-->0; )
  	{
  	  for (v=5; v-->0; )
  	    {
  	      if (PIX_WEIGHTS[TAB_0_25[u]+v] >= PIX_THRESH[TAB_0_25[u]+v])
  		fontm23[fontptr[charnum]+u]|=BTAB[v];
  	    }
  	}
    }
  else if ((pix_cnt < 54) || (pix_cnt >= 85))
    {
      // Algorithm B - Sparsely or heavily populated bitmaps
      for (u=16; u-->0; )
	{
	  for (v=8; v-->0; )
	    {
	      if (char_data[u] & (1<<v))
		{
		  fontm23[fontptr[charnum]+TAB_0_5i[u]]|=BTAB_5[v];
		}
	    }
	}
    }
  
}

This produces:

unknown.png

 

unknown.png

 

But certain bit patterns produce weird stipple like patterns (the N, the P, etc..), as seen here:

YQm7QKD.png

 

Versus: 

 

sr9xO5h.png

 

 

Anyone have an idea why this would be happening? I'm going to keep churning through it. 

 

-Thom



#16 Kyle22 OFFLINE  

Kyle22

    River Patroller

  • 3,612 posts
  • Call my BBS! telnet://broadway1.lorexddns.net
  • Location:McKees Rocks (Pittsburgh), PA

Posted Sat Jul 28, 2018 8:04 PM

Could it be related to character cell size and the algorithm? Math pack floating point error?


Edited by Kyle22, Sat Jul 28, 2018 9:33 PM.


#17 _The Doctor__ OFFLINE  

_The Doctor__

    Quadrunner

  • 5,224 posts
  • Location:10-0-11-00:02

Posted Sat Jul 28, 2018 11:18 PM

The relationship of the starting char set grid row and columns from one computer to another requires the transform algorithm to be tweaked and the preference affinity be adjusted. While a troglodyte such as myself couldn't possibly know anything about such things, the precision of the math pack (if floating point is used could affect the output) but that's a theoretical thing not necessarily directed about anything in this instance. It is an outlier. 

 

When looking at the output I see choices that do not match up possibly because it's origin 'tlp perhaps' knows nothing of the extra pixels (cells) involved. Or for some machines, the lack of (pixels) cells involved.

 

it might also be noted the typography from machine to machine is changed, as the normal rules for the Atari were changed using the char grid from edge to edge.

 

while it might not be completely useful, you might find this page interesting, and the comments below from some others who were in ranks on this sort of thing... be advised that remembrance is not always perfect and there may be a misstatement or two (please forgive that) but it close enough to shed light on some fascinating font finesse

https://damieng.com/...ts-system-fonts

 

the percentage of pixels in each character grid is different because the ratio has changed depending on the target machine, the choice for which method of transform by pixel count may need to be adjusted.

 

While I could go on further, I'm probably just full of it or something and really shouldn't post such things. It's just my empty head dreaming up stuff I'm sure. My  memory is not the best, and I really haven't looked at the math too deeply, might be some mistake....


Edited by _The Doctor__, Sat Jul 28, 2018 11:40 PM.


#18 tschak909 OFFLINE  

tschak909

    River Patroller

  • Topic Starter
  • 2,783 posts
  • Location:USA

Posted Thu Aug 2, 2018 10:16 AM

16kRAM took a whack at the algorithm, and I folded in the functional changes...

 

The sparse characters now mostly render correctly, but those that are borderline dense now completely fail due to the xor...which is odd, because the algorithm deliberately tries to account for that...

 

https://gist.github....79c3a6d3fb03776

 

03-checkers1.PNG

 

04-checkers2.PNG

 

compared to TLP:

 

05-checkers1.PNG

 

06-checkers2.PNG

 

I am documenting the @#(%@#(% out of this for others to understand...






0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users