mintlib could use optimised string functions

[mikrosk]

https://atari-forum.com/viewtopic.php?p=487883#p487883 reminded me: why don't we use asm versions of the most common string functions like strcpy, strncpy, strcmp etc? It would help both mintlib and libcmini and we wouldn't need to fear that some GCC options makes it really inefficient.

[th-otto]

I think we don't always need asm versions. For example,

size_t strlen(const char *scan)
{
	const char *start = scan;

	while (*scan++ != '\0')
		continue;
	return scan - start - 1;
}

Produces

[00000000] 202f 0004                 move.l     4(a7),d0
[00000004] 2040                      movea.l    d0,a0
.L2:
[00000006] 4a18                      tst.b      (a0)+
[00000008] 66fc                      bne.s      .L2
[0000000a] 91c0                      suba.l     d0,a0
[0000000c] 2008                      move.l     a0,d0
[0000000e] 5380                      subq.l     #1,d0
[00000010] 4e75                      rts

With all compilers that i tried. It also produces just a constant when passing a constant string. The actual code is 6 instructions, which should always be shorter than a function call that has to push/pop parameters. So all we need to do in this case is to provide something like

_EXTERN_INLINE size_t __inline_strlen(const char *scan);
_EXTERN_INLINE size_t __inline_strlen(const char *scan)
{
	const char *start = scan;

	while (*scan++ != '\0')
		continue;
	return scan - start - 1;
}
#ifdef __OPTIMIZE__
#define strlen(s) __inline_strlen(s)
#endif

in string.h

Note: my first attempt was to declare it as static inline. But then, gcc complains
error: '__inline_strlen' is static but used in inline function '__argp_fmtstream_puts' which is not static
???

[mikrosk]

Doesn't it have something to do with the fact that we explicitely force the gnu89 inlining? (just a random guess)

And you are right, the generated code looks good. Interesting how wildly different the results are for stuff like *dst++ = *src++.

[th-otto]

Doesn't it have something to do with the fact that we explicitely force the gnu89 inlining?

Strangely not. gnu89 inline is defined as part of _EXTERN_INLINE. When i replace that with something like static __inline i get the above mentioned error.

[th-otto]

Interesting how wildly different the results are for stuff like *dst++ = *src++.

Yes, other functions have to be checked. The link above already mentions some cases where different compilers produce different code. In that case, it would actually be better to use inline asm. But then you also have to take into account cases where one of the arguments is a constant (i guess this will happen quite a lot for strcmp)

[th-otto]

I always wondered whether the special treatment in strcmp() is really needed:

mintlib/string/strcmp.c

Lines 29 to 42 in 1d7e5ee

	/*
	* The following case analysis is necessary so that characters
	* which look negative collate low against normal characters but
	* high against the end-of-string NUL.
	*/
	if (c1 == c2)
	return(0);
	else if (c1 == '\0')
	return(-1);
	else if (c2 == '\0')
	return(1);
	else
	return(c1 - c2);
	}

Imho that can just be the default return c1 - c2, because the local variables c1 and c2 are unsigned.

Considering the cases:

• c1 == c2 will return 0 in both cases
• c1 == 0 (and c2 != 0) will return a negative value in both cases, no matter whether c2 is >= 128 or not
• c2 == 0 (and c1 != 0) will return a positive value in both cases, no matter whether c1 is >= 128 or not

Or did i miss something???

[th-otto]

Hm for strlen, the C-code does not produce optimal code in all cases. for Example

char const h[] = "h";

int test(void)
{
	return strlen(h);
}

produces

        .globl  _test
_test:
        move.l #_h+1,%d0
        moveq #104,%d1
.L3:
        tst.b %d1
        jne .L6
        sub.l #_h+1,%d0
        rts
.L6:
        move.l %d0,%a0
        move.b (%a0)+,%d1
        move.l %a0,%d0
        jra .L3

So eventually it would really be better to use inline asm, to be sure.

[th-otto]

I've pushed the changes now. Could you please check whether there are any regressions in larger projects?

Similar patches are also done to libcmini .

[mikrosk]

At least your strlen change upset https://github.com/scummvm/scummvm/blob/a9d3a95328f896278a5a8bb2a7635c6df0dd9fa6/engines/sci/engine/seg_manager.h#L367 (strlen being a class method):

m68k-atari-mintelf-g++ -MMD -MF "engines/sci/.deps/console.d" -MQ "engines/sci/console.o" -MP -Wall -m68020-60 -DUSE_MOVE16 -DUSE_SUPERVIDEL -DUSE_SV_BLITTER -DDISABLE_LAUNCHERDISPLAY_GRID  -Wshadow -Wno-stringop-overflow -Wno-stringop-truncation -W -Wno-unused-parameter -Wno-empty-body -fno-operator-names -std=gnu++11 -pedantic -Wframe-larger-than=307200 -Wno-address-of-packed-member -fomit-frame-pointer -ffast-math -fno-unsafe-math-optimizations -O2 -Wuninitialized -Werror=return-type -Wno-long-long -Wno-multichar -Wno-unknown-pragmas -Wno-reorder -Wpointer-arith -Wcast-qual -Wnon-virtual-dtor -Wwrite-strings -fno-exceptions -fcheck-new -DHAVE_CONFIG_H -DRELEASE_BUILD -DSYSTEM_NOT_SUPPORTING_D_TYPE -D_GNU_SOURCE -DNDEBUG -DDISABLE_TEXT_CONSOLE -DREDUCE_MEMORY_USAGE -DDISABLE_NES_APU -DPOSIX -DDATA_PATH=\"/usr/local/share/scummvm\" -DPLUGIN_DIRECTORY=\"/usr/local/lib/scummvm\" -DENABLE_SCUMM=STATIC_PLUGIN -DENABLE_SCUMM_7_8 -DENABLE_HE -DENABLE_ACCESS=STATIC_PLUGIN -DENABLE_AGI=STATIC_PLUGIN -DENABLE_AGOS=STATIC_PLUGIN -DENABLE_AGOS2 -DENABLE_ASYLUM=STATIC_PLUGIN -DENABLE_AWE=STATIC_PLUGIN -DENABLE_BBVS=STATIC_PLUGIN -DENABLE_CGE=STATIC_PLUGIN -DENABLE_CGE2=STATIC_PLUGIN -DENABLE_CHEWY=STATIC_PLUGIN -DENABLE_COMPOSER=STATIC_PLUGIN -DENABLE_CRUISE=STATIC_PLUGIN -DENABLE_CRYOMNI3D=STATIC_PLUGIN -DENABLE_VERSAILLES -DENABLE_DARKSEED=STATIC_PLUGIN -DENABLE_DGDS=STATIC_PLUGIN -DENABLE_DRACI=STATIC_PLUGIN -DENABLE_DRASCULA=STATIC_PLUGIN -DENABLE_DREAMWEB=STATIC_PLUGIN -DENABLE_EFH=STATIC_PLUGIN -DENABLE_GOB=STATIC_PLUGIN -DENABLE_GOT=STATIC_PLUGIN -DENABLE_GROOVIE=STATIC_PLUGIN -DENABLE_HADESCH=STATIC_PLUGIN -DENABLE_HYPNO=STATIC_PLUGIN -DENABLE_ILLUSIONS=STATIC_PLUGIN -DENABLE_KINGDOM=STATIC_PLUGIN -DENABLE_KYRA=STATIC_PLUGIN -DENABLE_LOL -DENABLE_EOB -DENABLE_LAB=STATIC_PLUGIN -DENABLE_LURE=STATIC_PLUGIN -DENABLE_M4=STATIC_PLUGIN -DENABLE_MADE=STATIC_PLUGIN -DENABLE_MADS=STATIC_PLUGIN -DENABLE_MM=STATIC_PLUGIN -DENABLE_MM1 -DENABLE_XEEN -DENABLE_MOHAWK=STATIC_PLUGIN -DENABLE_MYST -DENABLE_MORTEVIELLE=STATIC_PLUGIN -DENABLE_NEVERHOOD=STATIC_PLUGIN -DENABLE_PARALLACTION=STATIC_PLUGIN -DENABLE_PINK=STATIC_PLUGIN -DENABLE_PLUMBERS=STATIC_PLUGIN -DENABLE_PRINCE=STATIC_PLUGIN -DENABLE_PRIVATE=STATIC_PLUGIN -DENABLE_QUEEN=STATIC_PLUGIN -DENABLE_SAGA=STATIC_PLUGIN -DENABLE_IHNM -DENABLE_SAGA2=STATIC_PLUGIN -DENABLE_SCI=STATIC_PLUGIN -DENABLE_SCI32 -DENABLE_SHERLOCK=STATIC_PLUGIN -DENABLE_SKY=STATIC_PLUGIN -DENABLE_SUPERNOVA=STATIC_PLUGIN -DENABLE_SWORD1=STATIC_PLUGIN -DENABLE_SWORD2=STATIC_PLUGIN -DENABLE_TEENAGENT=STATIC_PLUGIN -DENABLE_TINSEL=STATIC_PLUGIN -DENABLE_TOLTECS=STATIC_PLUGIN -DENABLE_TOON=STATIC_PLUGIN -DENABLE_TOT=STATIC_PLUGIN -DENABLE_TOUCHE=STATIC_PLUGIN -DENABLE_TSAGE=STATIC_PLUGIN -DENABLE_RINGWORLD -DENABLE_BLUEFORCE -DENABLE_RINGWORLD2 -DENABLE_TUCKER=STATIC_PLUGIN -DENABLE_TWINE=STATIC_PLUGIN -DENABLE_VOYEUR=STATIC_PLUGIN -DENABLE_WAGE=STATIC_PLUGIN -I. -I.. -I../engines -c ../engines/sci/console.cpp -o engines/sci/console.o
In file included from ../common/scummsys.h:86,
                 from ../common/md5.h:25,
                 from ../engines/sci/console.cpp:24:
../engines/sci/engine/seg_manager.h:367:16: error: expected ')' before '?' token
  367 |         size_t strlen(reg_t str);
      |                ^~~~~~
make: *** [../Makefile.common:177: engines/sci/console.o] Error 1

You could also try running all the mintlib tests to make sure that none of them breaks with your new implementation?

[th-otto]

Hm, that is bad. I tried to move the __builtin_constant_p() check into the inline function, but that does not seem to work. The reason for using is if you do something like strlen("hello"), which should just compile into a constant and not into the loop.
Similar for common practise like doing strcpy(buf, ""), which should just compile into a single move.

Any idea how to solve that? Of course i could just use something like#if defined(__OPTIMIZE__) && !defined(__cplusplus), but then you loose that optimization in all c++ code.

You could also try running all the mintlib tests

Are there any? ;) But i did run the ones in libcmini.

[mikrosk]

Are there any? ;) But i did run the ones in libcmini.

Yes, check out all those test-*.c files.

[th-otto]

Ah ok. But unfortunately, make check does not work when cross-compiling. We should find a way to run the tests in hatari. Then we could add that target also to the snapshot builds.

I ran them manually now, and did not find any problems related to the changes.

There were some problems though when trying to run a complete make check on aranym. speeds in the crypt directory seems to hang (not a regression though), and some tests that include <math.h> fail to compile (this is because they are compiled with -nostdinc, and math.h is no longer part of mintlib).

Edit: most of the tests are fixed now. Some still hang in aranym (test-clock and speeds), but that has nothing to do with the changes here. Will open a separate issue for that. Maybe you can also have a look at it. Both seem to be related to trying to set an alarm timer and catching SIGALRM.

Edit2: that seems to be a problem in the kernel, not mintlib. The signal function is never called.

[mikrosk]

Good, having the tests (or most of them) fixed/compilable again is a nice bonus.

As for the original problem -- do I understand it correctly that the problem is the #define strlen ... ? So it's replaced in real source code with seg_manager->(all that built-in stuff) ? If so, C++ isn't the only problem. You can have something like

struct S {
  char* str;
  int strlen; // because I like to store strlen results like this
}

After a few experiments I have managed to nail it down to this:

#include <stddef.h>

#ifdef __cplusplus
extern "C" {
#endif

extern __inline__ __attribute__((__gnu_inline__)) size_t strlen(const char *__scan)
{
	const char *__start = __scan;
	__asm__ __volatile__(
		"1:\n"
		" tst.b (%0)+\n"
		" bne.s 1b"
	: "+a"(__scan)
	:
	: "cc");
	return __scan - __start - 1;
}

#ifdef __cplusplus
}
#endif

int f(const char *s) {
    int a = strlen("aaa");
    int b = strlen(s);
    return a + b;
}

This produces:

f(char const*):
        move.l 4(%sp),%d0
        move.l %d0,%a0
| 10 "/app/example.cpp" 1
        1:
 tst.b (%a0)+
 bne.s 1b
| 0 "" 2
        sub.l %d0,%a0
        move.l %a0,%d0
        addq.l #2,%d0
        rts

The key seemed to be to specify the C linkage.

[th-otto]

As for the original problem -- do I understand it correctly that the problem is the #define strlen ... ? So it's replaced in real source code with seg_manager->(all that built-in stuff) ?

Yes, exactly.

int strlen; // because I like to store strlen results like this

That would still have worked, since the macro takes parameters, so the identifier by itself is not replaced

After a few experiments I have managed to nail it down to this:

Hm strangely yes, that seems to work. Even for constant strings. Only drawback: the inline version has to be copied also to the implementation.

And it only partly works for strcpy. When i do the same for it, something like

	strcpy(buf, "hello");

Still expands to the __builtin_strcpy() version:

        move.b #104,_buf
        move.b #101,_buf+1
        move.b #108,_buf+2
        move.b #108,_buf+3
        move.b #111,_buf+4
        clr.b _buf+5

That might be slightly faster, but produces a lot of code. And when the string gets longer, it is expanded to a memcpy() library call :(

So unless a similar problem pops up for strcpy(), i will leave it as it currently is.

BTW, i've looked into running the tests with Hatari. Basically, it should be something like

SDL_VIDEODRIVER=dummy SDL_AUDIODRIVER=dummy hatari --log-level fatal --fast-forward on --machine ste --sound off --run-vbls 1000 --tos none ./test-strcmp

But then i get

ERROR: Unhandled exception!

Seems to be the Drvmap() call from the startup code. When i disable that, i get the next error message:

FATAL: GEMDOS 0x42 Fseek at PC 0xACCC unsupported in test mode

Probably from some isatty() call. Fixed that in Hatari. Then i get:

FATAL: GEMDOS 0x48 Malloc at PC 0xA170 unsupported in test mode

Dunno where that is from, maybe from some fopen call? Atleast that is the point where i gave up for now.

[th-otto]

Atleast that is the point where i gave up for now.

Partly solved (see also post on Hatari mailing list). Some programs can now be run.

Now have to check which programs can be run, and which not (test-clock for example won't work, because hz_200 never changes without a real tos).

[mikrosk]

--tos none

I wonder, is this worth fighting against? Wouldn't be easier just to use EmuTOS?