Most efficient ToUpper function in BBC BASIC?

[Lardo Boffin]

I am looking for an efficient (small / fast) implementation of a function to convert a string to upper case. The function only expects text so I am not too fussed about checking for special characters etc.

The best I have so far is:

DEFFNtU(T$):LOCAL C%,P%,L%:M$="":L%=LEN(T$):FOR P%=1 TO L%:C%=ASC(MID$(T$,P%,1)):C%=C%+((C%>90)*32):M$=M$+CHR$(C%):NEXT:=M$

I’m not at the beeb so the syntax might be slightly wrong!

M$ is defined elsewhere as a string of 256 chars to avoid it growing in use.

I may be able to combine the lower case check with the M$=M$+ section looking at it. E.g.

M$=M$+CHR$(C%+((C%>90)*32)) to save a couple of bytes.

Is there a better way with bitwise operations or other methods to take 32 off when the ASCII value is greater than 90 (i.e. lower case)?

Also does the beeb evaluate the TO condition on each loop?
So is FOR P%=1 TO L% any faster than FOR P%=1 TO LEN(T$)?
If they are the same speed I can get rid of L%.

[jms2]

Rather than doing

Code: Select all

C%=C%+((C%>90)*32)

, surely you could say this:

Code: Select all

C%=C% AND &DF

This would force bit 5 to zero if it's high.

[Lardo Boffin]

Thanks. Will give that a go. I figured there was probably a bitwise way of doing it but can never quite seem to get my head round it in BASIC.

[lurkio]

M$ is defined elsewhere as a string of 256 chars to avoid it growing in use.

A gotcha to watch out for (I think!?): if you're using STRING$ to initially define M$, then the length param should be 255, not 256:

Code: Select all

10 M$=STRING$(255,"x")
20 PRINT M$'LEN(M$)
30 M$=STRING$(256,"x")
40 PRINT M$'LEN(M$)

[Lardo Boffin]

M$ is defined elsewhere as a string of 256 chars to avoid it growing in use.

A gotcha to watch out for (I think!?): if you're using STRING$ to initially define M$, then the length param should be 255, not 256:

Code: Select all

10 M$=STRING$(255,"x")
20 PRINT M$'LEN(M$)
30 M$=STRING$(256,"x")
40 PRINT M$'LEN(M$)

You are probably right! The last character should doubtless be the carriage return therefore only giving 255 chars to use?

[Lardo Boffin]

Maybe this?

Code: Select all

DEFFNtU(T$):LOCAL P%:M$="":FOR P%=1 TO LEN(T$):M$=M$+CHR$(ASC(MID$(T$,P%,1)) AND &DF):NEXT:=M$

Might not have the syntax quite right.

[Mince]

Veering off topic, if you have a lot of strings to do, you can crowbar in a bit of 6502 with CALL.

On my native Master 65C12, 50 conversions of the string below take 28.36s in BASIC but 0.2s using the 6502 version (which does upper case it in place, so you must copy it first, if you don't want to destroy the original string) - and it doesn't check if you don't just give it a single string parameter, so it's likely to crash horribly, then.

What was also interesting was how much various compression techniques on the code affect speed...

Putting in your FNtU instead of my FNupper took 14.84s. If I took the check for non lower-case letters out of my FNupper, it took 24.26s. If I then compressed the loop to just "r$=r$+CHR$(ASC(MID$(s$,n%,1)) AND &DF)" (i.e. combining the three lines) then it took 20.07s, so there's a 5.2s penalty for spacing it out across lines.

Anyway, probably not what you want but it is a mental exercise and might be interesting.

Code: Select all

REM>UpperStr
DIM code% 50
scratch=&70
paramblk=&600
:
s$="Mince pies are nice because of their lovely mincey taste, said Mr Mince."
:
FOR pass%=0 TO 1
P%=code%
[ OPT pass%*2
\ get addr of string paramblk
\ into scratch
LDA paramblk+1
STA scratch
LDA paramblk+2
STA scratch+1
\ get string addr in paramblk
\ into scratch+2
LDY #0
LDA (scratch),Y
STA scratch+2
INY
LDA (scratch),Y
STA scratch+3
\ get current len of string to Y
LDY #3
LDA (scratch),Y
TAY
.loop
\ have we done all characters?
CPY #0
BEQ done
\ no - move back to next last
DEY
LDA (scratch+2),Y
CMP #ASC("a")
BCC loop
CMP #ASC("z")+1
BCS loop
\ lower-case - change to upper
AND #&DF
STA (scratch+2),Y
JMP loop
.done
RTS
]
NEXT
:
start%=TIME
FOR i%=1 TO 50
t$=FNupper(s$)
NEXT
PRINT ;(TIME-start%)/100;"s"
:
start%=TIME
FOR i%=1 TO 50
t$=s$
CALL code%,t$
NEXT
PRINT ;(TIME-start%)/100;"s"
END
:
DEFFNupper(s$)
LOCAL r$,n%,c%
r$=""
FOR n%=1 TO LEN(s$)
c%=ASC(MID$(s$,n%,1))
IF c%>=97 AND c%<=126 THEN c%=c% AND &DF
r$=r$+CHR$(c%)
NEXT
=r$

There're probably some mistakes in there.

[Lardo Boffin]

Its interesting that with the extra lines it is about 20% slower.
Its logical that it would be slower as there are extra bytes to process but that much is quite a surprise!

[Mince]

(Following my post-work afternoon tea...) Here's another way to bouff it up, but staying in BASIC using a buffer to avoid that messy string slicing/appending and ASC() and CHR$() conversion:

Code: Select all

DIM r% 256 : REM do this once at the start

DEFFNupper2(s$)
LOCAL n%,c%
$r%=s$
FOR n%=0 TO LEN(s$)-1
c%=r%?n%
IF c%>=97 AND c%<=122 THEN r%?n%=c% AND &DF
NEXT
=$r%

(Sorry, the 126 in my previous code should have been a 122.)

This takes 12.17s; remove the lower case check and it comes down to 9.32s. Squeezing it onto one line gets it down to 6.06s:

Code: Select all

DEFFNtU(s$):LOCAL n%:$r%=s$:FOR n%=0 TO LEN(s$)-1:r%?n%=r%?n% AND &DF:NEXT:=$r%

Take the spaces out and you'll get a few more hundredths - 5.99s for me.

[Richard Russell]

I've not benchmarked this, but avoiding string functions may give better results:

Code: Select all

   10 DIM T% 255
   20 PRINT FNtU("Hello world!")
   30 END
   40
   50 DEFFNtU($T%):LOCALP%:FORP%=T%TOT%+LEN$T%:?P%=?P%+&20*(?P%>&60):NEXT:=$T%

Sorry about the global variable T%. I tried to use the string accumulator at &600 but it doesn't work.

[Richard Russell]

surely you could say this:

Code: Select all

C%=C% AND &DF

This would force bit 5 to zero if it's high.

That's not what you want for a ToUpper function because it will corrupt characters &20 to &3F (" " to "?").

[Coeus]

surely you could say this:

Code: Select all

C%=C% AND &DF

This would force bit 5 to zero if it's high.

That's not what you want for a ToUpper function because it will corrupt characters &20 to &3F (" " to "?").

This 'AND &DF' is quite commonly used in the OS and service ROMs when comparing characters from what should be a command name with characters from a command lookup table. Here, the fact that some non-alpha characters will be changed into other non-alpha characters doesn't matter because the command table only contains alpha characters so these non-alphas will not match anything in their altered form just as well as they would not match anything in their original form.

So, in limited circumstances, it is a useful trick and fast but one needs to know the limitations.

[Richard Russell]

This 'AND &DF' is quite commonly used in the OS and service ROMs when comparing characters from what should be a command name with characters from a command lookup table.

Indeed, because only a limited subset of the character set is involved (although in my own applications of the same principle I more commonly use OR &20 to convert capital letters to lowercase, which I compare with a table of lowercase commands, because that preserves &20 to &3F).

But that's not what the ToUpper() function - which is what the title of this thread explicitly refers to - does. Strictly it should only modify a-z (and accented versions thereof in some implementations).

[Kweepa]

Code: Select all

0DIMT%255
1T$="HelloWorld!":T$=STRING$(23,T$):T=TI.
2T$=FNtU(T$)
4P.;(TI.-T)/100;"sec to get ";T$:END
5DEFFNtU($T%):LOCALP%,W%,X%,Y%,Z%:X%=32:Y%=96:Z%=123:FORP%=T%TOT%+LEN$T%:?P%=?P%+X%*(?P%>Y%A.?P%<Z%):NEXT:=$T%

Based on Richard Russell's code (with another check to not screw up {|}~), this takes 0.68sec for 253 characters.

[Lardo Boffin]

Does it run faster declaring the 32, 96 and 123 as integer variables? Presumably it means that BASIC doesn’t have to convert the typed numbers into an actual number each time for the comparison?

[Kweepa]

Yes, it was a smidgen (~0.06sec) faster that way, for the reason you state.

[jgharston]

What does FNtU("") give you?

If you're going for two-letter function names, I find FNuc() FNlc() more semantically "better".

It's a function, so it's an adjective, you get the SIN of something, you don't to-SIN something, you get the UpperCase of something, you don't get the to-upper-case of something.

Procedures are commands, so t(o)u(pper) would be an appropriate name for a procedure, because you're telling it so do something. PROCprint - print something for me, PROCreverse - reverse something for me, PROCtoupper - changes something to upper for me.

[Richard Russell]

Yes, it was a smidgen (~0.06sec) faster that way, for the reason you state.

I would expect it to depend on the length of the string. With a sufficiently short string making the temporary variables LOCAL might take longer than the saving in the loop.

[Richard Russell]

you get the SIN of something, you don't to-SIN something

You convert something to uppercase, you don't uppercase it or get the uppercase of it!

[Lardo Boffin]

What does FNtU("") give you?

I suspect it will crash as it tries to get data from a position in a string that does not exist.

In my usage scenario this is extremely unlikely to occur however. It is called in two places - one is where data is loaded into memory, in this case verbs, nouns and object names etc for an adventure framework parser. These will never be blank (unless someone hacks one of the files in which case it serves them right). Two is where the command entered by the player is broken up into words and tokenised. Only words are passed through to the function so if the player just pressed enter or typed in a load of spaces nothing will get as far as the function.

If you're going for two-letter function names, I find FNuc() FNlc() more semantically "better".

It's a function, so it's an adjective, you get the SIN of something, you don't to-SIN something, you get the UpperCase of something, you don't get the to-upper-case of something.

Procedures are commands, so t(o)u(pper) would be an appropriate name for a procedure, because you're telling it so do something. PROCprint - print something for me, PROCreverse - reverse something for me, PROCtoupper - changes something to upper for me.

I think I got the function name from using it in C and quite possibly C#.

[Richard Russell]

I suspect it will crash as it tries to get data from a position in a string that does not exist.

My code will work fine and return an empty string, as one would expect. I deliberately looped through the terminating CR as well as the string, since the conversion to lowercase (even if done the crude AND &5F way) will leave it unchanged. If you supply an empty string it will loop just once, looking at (but not modifying) the CR, and return an empty string to the caller.

[Richard Russell]

Code: Select all

0DIMT%255
1T$="HelloWorld!":T$=STRING$(23,T$):T=TI.
2T$=FNtU(T$)
4P.;(TI.-T)/100;"sec to get ";T$:END
5DEFFNtU($T%):LOCALP%,W%,X%,Y%,Z%:X%=32:Y%=96:Z%=123:FORP%=T%TOT%+LEN$T%:?P%=?P%+X%*(?P%>Y%A.?P%<Z%):NEXT:=$T%

Based on Richard Russell's code (with another check to not screw up {|}~), this takes 0.68sec for 253 characters.

Your code, like mine, has a potential 'nasty' because the first thing BASIC tries to do when the function is called is to save the string $T% used as the formal parameter, but that string has no terminating CR. It would be safer to change the first line to:

Code: Select all

DIM T% 255 : ?T%=&D

or equivalently:

Code: Select all

DIM T% 255 : $T%=""

[Mince]

I'm intrigued by this use of an indirection operator in a DEFFN — I've never seen that before; where's that documented? It seems to copy the bytes representing the variable (or explicit string/number) into the buffer whose address is given, instead of populating a local variable.

It also doesn't work with DEFPROC, which seems a bit odd.

Am I missing something really obvious here as to why I've never seen it, or is secret? It's certainly in the BASIC on my Master and obviously Richard knows what he's talking about here!

[Richard Russell]

I'm intrigued by this use of an indirection operator in a DEFFN — I've never seen that before; where's that documented?

I don't know that it's documented explicitly, but it shouldn't really need to be because in BBC BASIC indirection is treated exactly like a variable of the same type. So anywhere you can legally put A% you can put !P% or P%!Q%, and anywhere you can legally put S$ you should be able to put $P%. It is, for example, perfectly legitimate to put LOCAL !P% or LOCAL $P%.

It also doesn't work with DEFPROC, which seems a bit odd.

It should. A simplistic test works for me:

Code: Select all

   10 DIM T% 255
   20 $T% = "Outside"
   30 PROCtest("Inside")
   40 PRINT $T%
   50 END
   60
   70 DEF PROCtest($T%)
   80 PRINT $T%
   90 ENDPROC

[jms2]

That works for me too, in BeebEm.

I understand why it prints the first line of output ("Inside"), but at first I was struggling to see what mechanism resets the contents of the global buffer at T% to "Outside" after exitting the procedure. I assume that it can't be affecting the global variable - is it making a local variable to contain the string instead?

[Richard Russell]

I was struggling to see what mechanism resets the contents of the global buffer at T% to "Outside" after exitting the procedure.

It's simply doing what it normally would with a 'conventional' formal parameter (i.e. a variable) which is first to save it - probably on the stack, but that's implementation-dependent - then copy the actual parameter into the formal parameter, and then on exit from the FN/PROC restore the formal parameter to its original value. This is what you might more commonly expect to see:

Code: Select all

   20 T$ = "Outside"
   30 PROCtest("Inside")
   40 PRINT T$
   50 END
   60
   70 DEF PROCtest(T$)
   80 PRINT T$
   90 ENDPROC

The only differences in my previous listing are that the string variable T$ has been replaced by the 'fixed string' $T% throughout, but otherwise everything works just the same internally. This helps to illustrate how sophisticated BBC BASIC was in 1981.

[Richard Russell]

I assume that it can't be affecting the global variable - is it making a local variable to contain the string instead?

BBC BASIC doesn't have true 'local variables' (as C and other languages do); all variables in BBC BASIC are 'global' in the sense that they have global scope and once created they can be seen anywhere in the program. The LOCAL statement doesn't create a local variable (despite its name), rather it creates a global variable but makes it appear to be local by temporarily storing its original value and then restoring it on exit.

This distinction can be important in a couple of circumstances. Firstly if an error occurs in an FN or PROC any LOCAL variables (and formal parameters) will retain the values they had inside the FN/PROC - they will become 'global' (true local variables would be discarded in these circumstances). I have introduced the RESTORE LOCAL statement in my versions of BBC BASIC to work around this behaviour when it's not wanted.

Secondly, if assembly language code looks at the value of a global variable in an interrupt routine, if the interrupt happens to occur whilst a LOCAL variable of the same name is active the assembler code will see the 'local' value, not the 'global' value! This same thing can happen even in BASIC in the case of my versions, because they support 'interrupts' with the ON <event> syntax (e.g. ON TIME).

[Mince]

That's really interesting, thanks for the explanation. I wrote this program to nose further:

Code: Select all

   10 S%=10
   20 DIM T% S%
   30 $T%="MAIN PROG"
   40 PRINT $T%
   50 PROCdump(T%,S%)
   60 PROCin("PROC")
   70 PRINT $T%
   80 PROCdump(T%,S%)
   90 END
  100 :
  110 DEFPROCin($T%)
  120 PRINT $T%
  130 PROCdump(T%,S%)
  140 ENDPROC
  150 :
  160 DEFPROCdump(M%,L%)
  170 LOCAL N%
  180 PRINT ;~M%;
  190 FOR N%=0 TO L%-1
  200 PRINT " ";
  210 IF M%?N%>=33 AND M%?N%<=126 THEN VDU M%?N% ELSE PRINT "<";RIGHT$(STR$~(M%?N% OR &100),2);">";
  220 NEXT
  230 PRINT
  240 ENDPROC

When run, it prints:

Code: Select all

MAIN PROG
93A M A I N <20> P R O G <0D>
PROC
93A P R O C <0D> P R O G <0D>
MAIN PROG
93A M A I N <20> P R O G <0D>

... which shows just the 5 bytes ("PROC" + CR) are overwriting the buffer at T%, when the procedure is called.

Conversely, if I change the 'in procedure' text to be longer than the out of procedure one (e.g. "MAIN" and "PROCEED") then I get:

Code: Select all

MAIN
938 M A I N <0D> N <20> P R O
PROCEED
938 P R O C E E D <0D> R O
MAIN
938 M A I N <0D> E D <0D> R O

... which shows only the 5 string bytes of the T% buffer are saved, when the procedure is entered.

I'm unsure why this didn't work with procedures yesterday — I assume I was doing something stupid.

Thanks again. This might all fit into place if I learnt BCPL, but it's not at the top of my list!

[Richard Russell]

When run, it prints:

Code: Select all

MAIN PROG
93A M A I N <20> P R O G <0D>
PROC
93A P R O C <0D> P R O G <0D>
MAIN PROG
93A M A I N <20> P R O G <0D>

Here's what I get when I run your code in BBC BASIC for SDL 2.0:

Code: Select all

MAIN PROG
D9A1DF8 M A I N <20> P R O G <0D>
PROC
D9A1DF8 P R O C <0D> P R O G <0D>
MAIN PROG
D9A1DF8 M A I N <20> P R O G <0D>

So although BBC BASIC has come a long way since 1981 the fundamentals work exactly the same now as they did then!

[Lardo Boffin]

I assume that it can't be affecting the global variable - is it making a local variable to contain the string instead?

BBC BASIC doesn't have true 'local variables' (as C and other languages do); all variables in BBC BASIC are 'global' in the sense that they have global scope and once created they can be seen anywhere in the program. The LOCAL statement doesn't create a local variable (despite its name), rather it creates a global variable but makes it appear to be local by temporarily storing its original value and then restoring it on exit.

Thanks. Although I think I had read that somewhere before I had forgotten it and was assuming wrongly I wasn’t taking up permanent storage in RAM with locals, i.e. they were maybe saved somewhere temporarily and then forgotten once the PROC exited.

I think I will review my use of them.

BBC BASIC is an endlessly fascinating language!