Contact us Heritage collections Image license terms
HOME ACL Associates Technology Literature Applications Society Software revisited
Further reading □ Overview □ No.1 □ No.2 □ No.3 □ No.4 □ No.5 □ No.8 □ No.9 □ No.11 □ No.12 □ No.13 □ No.14 □ No.15 □ No.17 □ No.19 □ No.21 □ No.22 □ No.23 □ No.24 □ No.25 □ No.26 □ No.27 □ No.28 □ No.29 □ No.30 □ No.31 □ No.32 □ No.33 □ No.37 □ No.38 □ No.39 □ No.40 □ No.41 □ No.43 □ No.44 □ No.45 □ No.46 □ No.47 □ No.48 □ No.49 □ No.50 □ No.51 □ No.52
ACD C&A INF CCD CISD Archives Contact us Heritage archives Image license terms

Search

   
⟶ ACL ⟶ Literature ⟶ Progress Reports ⟶ SPROGS Papers
⟶ ACL ⟶ Literature ⟶ Progress Reports ⟶ SPROGS Papers
ACL ACD C&A INF CCD CISD Archives
Further reading ⇓

□ Overview
□ No.1
□ No.2
□ No.3
□ No.4
□ No.5
□ No.8
□ No.9
□ No.11
□ No.12
□ No.13
□ No.14
□ No.15
□ No.17
□ No.19
□ No.21
□ No.22
□ No.23
□ No.24
□ No.25
□ No.26
□ No.27
□ No.28
□ No.29
□ No.30
□ No.31
□ No.32
□ No.33
□ No.37
□ No.38
□ No.39
□ No.40
□ No.41
□ No.43
□ No.44
□ No.45
□ No.46
□ No.47
□ No.48
□ No.49
□ No.50
□ No.51
□ No.52

SPROGS Paper No 29: Character Font Storage

F R A Hopgood

December 11 1972

1. INTRODUCTION

We have already seen that the amount of stores required for character fonts is likely to be high. Currently the most compact font representation is going to take at least two words per line drawn as we assume that each line drawn in the character requires a DX,DY and V (visibility) to be specified. Using UPDX and UPDY for horizontal and vertical lines it is possible to make some saving. The purpose of this note is to describe a method of font storage which could take a lot less space. Although this may not be immediately available in SPROGS as it stands in an efficient manner, minor changes would certainly make. it attractive. The ideas expressed here are not new but derive from a paper by R Suzuki, K Ikeda and T Kiyono in Information Processing in Japan Vol 11,1971.

2. DESCRIPTION OF CURRENT METHOD

Currently we define characters on a W×H grid. That is the characters can be at most W units wide and H units high with a maximum descending below the line of H/2. The letter A defined in a 16×16 grid might be: 

      TODXY(8,16) 
      TODXY(8,-16) 
      UPDXY(13,6) 
      TODX(10)
      UPDXY(3,-6)

The total possible different commands that can appear in a character definition on a 16×16 grid are 33×97 (the DX can be anything between -16 and +16 while the DY can be between -48 and +48). The minimum number of bits needed to specify each command is therefore 1 (visibility) + 6 (width) + 7 (height) = 14bits. This implies that there are 16384 different possibilities. In fact only 6402 are actually possible (2 × 33 × 97) due to the waste in the 6 bits allocated for width and 7 for height.

3. REDUCED FORM

Suppose we define a character font initially and then collect together all the possible commands that appear in the font. A number of characters will use the same commands. For example, a number of commands associated with the letters O and Q may be identical. Amalgamate all these commands into a file called FONT. Thus FONT might contain the commands: 

1     TODXY (8,16)   
2     TODXY (8,-16)   
3     TODXY ( 10,0)   
      . . . .   
      . . . .   
17   UPDXY (-13,6)   
      . . . .   
25   UPDXY (3, -6)

The order is unimportant to some extent. Assuming the font was defined originally as a set of UPDXY and TODY commands then the space taken up by the X and Y coordinates originally would be 2N. The numbering given above would be from 1 to N if all the commands were distinct and 1 to M where M<N if some commands are the same.

If we now assume that the FONT file is obeyed selectively depending on the entries in a null file which specifies each character then, for example, A would be defined as: 

      NULL(1) 
      NULL(2) 
      NULL(17) 
      NULL(3) 
      NULL(25)

The method of drawing A would now be more complex as it would be a matter of executing a subset of the commands in FONT depending on the entries in the null file. This can be done in SPROGS at the moment. However, the introduction of some special mechanisms for this purpose might be desirable.

4. ALTERNATIVE COMPACTING

Some other ideas which have not been fully worked out but which may be worth considering are:

(1) Symmetry

Picture files with symmetry about some axis could be specified by only 50% of the existing storage. For example, the character with symmetry about the origin in the Y direction might be drawn by first going through the file executing the commands and then retrace through the file backwards replacing X by -X in each command.

(2) Positions

If the scheme outlined above is not efficient due to too many commands being specified in the font an alternative is to define the characters by the particular absolute points used in the characters rather than the relative positions. If the number of absolute points on the mesh actually used in character forms is much less than the total set then storage saving will take place.

(3) Subpictures

A number of characters are made up of subpictures. For example, a Q is an O with an extra line. AG is a C with additional lines. The letters 'p' and 'b' may have the same connected curve with either an upward or downward stalk. In this case characters can be defined containing DRAW calls to the separate sub-items (to some extent the initial proposal could be implemented in this way with each command in FONT being defined as a separate file!)

5. SUMMARY

The suggestions given above are unlikely to be implemented at the moment. However, they could influence what facilities are provided in SPROGS. To check the feasibility of this, it might be worth making an estimate of M for the one font already defined. Some thought could go into deciding whether this technique is likely to be of more general use than just character fonts.

⇑ Top of page
© Chilton Computing and UKRI Science and Technology Facilities Council webmaster@chilton-computing.org.uk
Our thanks to UKRI Science and Technology Facilities Council for hosting this site