Forums

help needed

Started by dew March 15, 2007
i need to implement any strng matching algorithm on a DSP processor
(TMS320Cxxxx).I will be using code composer studio.i can write the
algorithm in C and transfer it to the processor.Can anyone help me the
get the code of any string matching algorithm to be implemented on a
DSP processor.I would like it asap.its enough for me to compare jus a
few strings stored on the database.

Thanks a lot.

dew wrote:
> i need to implement any strng matching algorithm on a DSP processor > (TMS320Cxxxx).I will be using code composer studio.i can write the > algorithm in C and transfer it to the processor.Can anyone help me the > get the code of any string matching algorithm to be implemented on a > DSP processor.I would like it asap.its enough for me to compare jus a > few strings stored on the database.
From earlier messages, I suppose that you will be looking to match a password, presumably stored in consecutive memory locations, to a data base of allowed passwords. Before I set out to design an algorithm for this special case, I want you to confirm that my supposition is correct. One issue that will arise whatever you need to do is word size. I know of no byte-addressable DSP. A large database might encourage to pack the characters in it; that may be wise. If you do, you will need either to pack the string to be compared for comparison, or to unpack each database entry before (or while) you compare to it. Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
On Mar 16, 12:53 am, Jerry Avins <j...@ieee.org> wrote:
> dew wrote: > > i need to implement any strng matching algorithm on a DSP processor > > (TMS320Cxxxx).I will be using code composer studio.i can write the > > algorithm in C and transfer it to the processor.Can anyone help me the > > get the code of any string matching algorithm to be implemented on a > > DSP processor.I would like it asap.its enough for me to compare jus a > > few strings stored on the database. > > From earlier messages, I suppose that you will be looking to match a > password, presumably stored in consecutive memory locations, to a data > base of allowed passwords. > > Before I set out to design an algorithm for this special case, I want > you to confirm that my supposition is correct. One issue that will arise > whatever you need to do is word size. I know of no byte-addressable DSP. > A large database might encourage to pack the characters in it; that may > be wise. If you do, you will need either to pack the string to be > compared for comparison, or to unpack each database entry before (or > while) you compare to it. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF yes,u are right in your presumptions.and abt the wod size,whats going to deterrmine that? and i m guessing the packing will allow faster processing..
dew wrote:
> On Mar 16, 12:53 am, Jerry Avins <j...@ieee.org> wrote: >> dew wrote: >>> i need to implement any strng matching algorithm on a DSP processor >>> (TMS320Cxxxx).I will be using code composer studio.i can write the >>> algorithm in C and transfer it to the processor.Can anyone help me the >>> get the code of any string matching algorithm to be implemented on a >>> DSP processor.I would like it asap.its enough for me to compare jus a >>> few strings stored on the database. >> From earlier messages, I suppose that you will be looking to match a >> password, presumably stored in consecutive memory locations, to a data >> base of allowed passwords. >> >> Before I set out to design an algorithm for this special case, I want >> you to confirm that my supposition is correct. One issue that will arise >> whatever you need to do is word size. I know of no byte-addressable DSP. >> A large database might encourage to pack the characters in it; that may >> be wise. If you do, you will need either to pack the string to be >> compared for comparison, or to unpack each database entry before (or >> while) you compare to it. >> >> Jerry >> -- >> Engineering is the art of making what you want from things you can get. >> &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
> > yes,u are right in your presumptions.and abt the wod size,whats going > to deterrmine that? > and i m guessing the packing will allow faster processing..
Packing will save storage space, but the need to pack the string to be tested or to unpack the stored strings will cost time. Fore a very small data base, the code to deal with packing at run time may use about the same space that is saved. Not packing is simpler. If tight storage space is saved, it may be worth doing. Let me get the spec clear: 1) By some magic that doesn't concern us here, a string representing a password is obtained and placed in a buffer of known location. The string may be null terminated or be preceded by a count of its length. Null termination is standard C practice. A count at the beginning of the string expedites the comparison. 2) The database will presumably be designed to accommodate N entries of up to M characters each. There is no reason to use all of it by separating the entries by M characters regardless of their actual number. Such placement simplifies finding the start of a string. 3) A linear search for a match is appropriate for a small database. If the database is large, a binary search saves time but uses more code. The details of the matching algorithm should be simple enough, but I will outline them if the details are correct so far. Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
On Mar 16, 3:13 am, Jerry Avins <j...@ieee.org> wrote:
> dew wrote: > > On Mar 16, 12:53 am, Jerry Avins <j...@ieee.org> wrote: > >> dew wrote: > >>> i need to implement any strng matching algorithm on a DSP processor > >>> (TMS320Cxxxx).I will be using code composer studio.i can write the > >>> algorithm in C and transfer it to the processor.Can anyone help me the > >>> get the code of any string matching algorithm to be implemented on a > >>> DSP processor.I would like it asap.its enough for me to compare jus a > >>> few strings stored on the database. > >> From earlier messages, I suppose that you will be looking to match a > >> password, presumably stored in consecutive memory locations, to a data > >> base of allowed passwords. > > >> Before I set out to design an algorithm for this special case, I want > >> you to confirm that my supposition is correct. One issue that will ari=
se
> >> whatever you need to do is word size. I know of no byte-addressable DS=
P=2E
> >> A large database might encourage to pack the characters in it; that may > >> be wise. If you do, you will need either to pack the string to be > >> compared for comparison, or to unpack each database entry before (or > >> while) you compare to it. > > >> Jerry > >> -- > >> Engineering is the art of making what you want from things you can get. > >> =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF
> > > yes,u are right in your presumptions.and abt the wod size,whats going > > to deterrmine that? > > and i m guessing the packing will allow faster processing.. > > Packing will save storage space, but the need to pack the string to be > tested or to unpack the stored strings will cost time. Fore a very small > data base, the code to deal with packing at run time may use about the > same space that is saved. Not packing is simpler. If tight storage space > is saved, it may be worth doing. > > Let me get the spec clear: > > 1) By some magic that doesn't concern us here, a string representing a > password is obtained and placed in a buffer of known location. The > string may be null terminated or be preceded by a count of its length. > Null termination is standard C practice. A count at the beginning > of the string expedites the comparison. > > 2) The database will presumably be designed to accommodate N entries of > up to M characters each. There is no reason to use all of it by > separating the entries by M characters regardless of their actual > number. Such placement simplifies finding the start of a string. > > 3) A linear search for a match is appropriate for a small database. If > the database is large, a binary search saves time but uses more code. > > The details of the matching algorithm should be simple enough, but I > will outline them if the details are correct so far. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF- Hide qu= oted text -
> > - Show quoted text -
Yes, i will be storing only a few string on the database of specified length.and yes, linear search would do.and like u said, i don think packing is necessary.
dew wrote:

   ...

> Yes, i will be storing only a few string on the database of specified > length.and yes, linear search would do.and like u said, i don think > packing is necessary.
All right. Whether you use pointer arithmetic or array notation, set up the database to look like a two-dimensional array of chars; an array of strings. For linear search, null termination is nearly as efficient as a stored count and will probably produce simpler code. Making the string storage large enough to append a NULL to the longest entry will make a test for maximum length unnecessary. A NULL then always terminates the comparison. Set the database-entry index to zero (first element). Get the first character of the database entry. Of it is NULL go on to the next database entry. Without this test, a NULL password will pass unless all database entries contain valid passwords. 1) Set character index to zero. 2) Compare the indexed character of the buffer to the indexed character of the database entry. If they match, compare to NULL If it is NULL, you have a valid password; exit(FOUND) Otherwise, advance the character index Otherwise, advance the database-entry index; set the character index to zero 3) If the data-base index is still in bounds go to (2) Otherwise exit(NO_MATCH) Remarks: the buffer and data-base areas should be cleared to NULL before being loaded with data. (If it isn't data, it's NULL.) CAVEAT: I haven't actually coded this. Take it for what it's worth. -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
Jerry Avins wrote:
> dew wrote: > > ... > >> Yes, i will be storing only a few string on the database of specified >> length.and yes, linear search would do.and like u said, i don think >> packing is necessary. > > All right. Whether you use pointer arithmetic or array notation, set up > the database to look like a two-dimensional array of chars; an array of > strings. For linear search, null termination is nearly as efficient as a > stored count and will probably produce simpler code. Making the string > storage large enough to append a NULL to the longest entry will make a > test for maximum length unnecessary. A NULL then always terminates the > comparison. > > Set the database-entry index to zero (first element). > > Get the first character of the database entry. Of it is NULL go on to > the next database entry. Without this test, a NULL password will pass > unless all database entries contain valid passwords. > > 1) Set character index to zero. > > 2) Compare the indexed character of the buffer to the indexed character > of the database entry. > > If they match, compare to NULL > If it is NULL, you have a valid password; exit(FOUND) > Otherwise, advance the character index > Otherwise, advance the database-entry index; > set the character index to zero > > 3) If the data-base index is still in bounds go to (2) > Otherwise exit(NO_MATCH) > > Remarks: the buffer and data-base areas should be cleared to NULL before > being loaded with data. (If it isn't data, it's NULL.) > > CAVEAT: I haven't actually coded this. Take it for what it's worth.
A bug in the numbering, and an efficiency by reordering: 1) Set the database-entry index to zero (first element). 2) Set character index to zero. 3) Get the first character of the database entry. Of it is NULL go on to the next database entry. Without this test, a NULL password will pass unless all database entries contain valid passwords. 4) Compare the indexed character of the buffer to the indexed character of the database entry. If they match, compare to NULL If it is NULL, you have a valid password; exit(FOUND) Otherwise, advance the character index Otherwise, advance the database-entry index 5) If the data-base index is still in bounds go to (2) Otherwise exit(NO_MATCH) Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
On Mar 16, 10:59 pm, Jerry Avins <j...@ieee.org> wrote:
> Jerry Avins wrote: > > dew wrote: > > > ... > > >> Yes, i will be storing only a few string on the database of specified > >> length.and yes, linear search would do.and like u said, i don think > >> packing is necessary. > > > All right. Whether you use pointer arithmetic or array notation, set up > > the database to look like a two-dimensional array of chars; an array of > > strings. For linear search, null termination is nearly as efficient as a > > stored count and will probably produce simpler code. Making the string > > storage large enough to append a NULL to the longest entry will make a > > test for maximum length unnecessary. A NULL then always terminates the > > comparison. > > > Set the database-entry index to zero (first element). > > > Get the first character of the database entry. Of it is NULL go on to > > the next database entry. Without this test, a NULL password will pass > > unless all database entries contain valid passwords. > > > 1) Set character index to zero. > > > 2) Compare the indexed character of the buffer to the indexed character > > of the database entry. > > > If they match, compare to NULL > > If it is NULL, you have a valid password; exit(FOUND) > > Otherwise, advance the character index > > Otherwise, advance the database-entry index; > > set the character index to zero > > > 3) If the data-base index is still in bounds go to (2) > > Otherwise exit(NO_MATCH) > > > Remarks: the buffer and data-base areas should be cleared to NULL before > > being loaded with data. (If it isn't data, it's NULL.) > > > CAVEAT: I haven't actually coded this. Take it for what it's worth. > > A bug in the numbering, and an efficiency by reordering: > > 1) Set the database-entry index to zero (first element). > > 2) Set character index to zero. > > 3) Get the first character of the database entry. Of it is NULL go on to > the next database entry. Without this test, a NULL password will pass > unless all database entries contain valid passwords. > > 4) Compare the indexed character of the buffer to the indexed character > of the database entry. > > If they match, compare to NULL > If it is NULL, you have a valid password; exit(FOUND) > Otherwise, advance the character index > Otherwise, advance the database-entry index > > 5) If the data-base index is still in bounds go to (2) > Otherwise exit(NO_MATCH) > > Jerry > -- > Engineering is the art of making what you want from things you can get. > =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF Thank you very much for the replies and the answer.thanks again.
On Mar 16, 10:59 pm, Jerry Avins <j...@ieee.org> wrote:
> Jerry Avins wrote: > > dew wrote: > > > ... > > >> Yes, i will be storing only a few string on the database of specified > >> length.and yes, linear search would do.and like u said, i don think > >> packing is necessary. > > > All right. Whether you use pointer arithmetic or array notation, set up > > the database to look like a two-dimensional array of chars; an array of > > strings. For linear search, null termination is nearly as efficient as a > > stored count and will probably produce simpler code. Making the string > > storage large enough to append a NULL to the longest entry will make a > > test for maximum length unnecessary. A NULL then always terminates the > > comparison. > > > Set the database-entry index to zero (first element). > > > Get the first character of the database entry. Of it is NULL go on to > > the next database entry. Without this test, a NULL password will pass > > unless all database entries contain valid passwords. > > > 1) Set character index to zero. > > > 2) Compare the indexed character of the buffer to the indexed character > > of the database entry. > > > If they match, compare to NULL > > If it is NULL, you have a valid password; exit(FOUND) > > Otherwise, advance the character index > > Otherwise, advance the database-entry index; > > set the character index to zero > > > 3) If the data-base index is still in bounds go to (2) > > Otherwise exit(NO_MATCH) > > > Remarks: the buffer and data-base areas should be cleared to NULL before > > being loaded with data. (If it isn't data, it's NULL.) > > > CAVEAT: I haven't actually coded this. Take it for what it's worth. > > A bug in the numbering, and an efficiency by reordering: > > 1) Set the database-entry index to zero (first element). > > 2) Set character index to zero. > > 3) Get the first character of the database entry. Of it is NULL go on to > the next database entry. Without this test, a NULL password will pass > unless all database entries contain valid passwords. > > 4) Compare the indexed character of the buffer to the indexed character > of the database entry. > > If they match, compare to NULL > If it is NULL, you have a valid password; exit(FOUND) > Otherwise, advance the character index > Otherwise, advance the database-entry index > > 5) If the data-base index is still in bounds go to (2) > Otherwise exit(NO_MATCH) > > Jerry > -- > Engineering is the art of making what you want from things you can get. > =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF When i implement this on a DSP processor, are there any specific problems i will encounter.(of course, assuming that it has been coded correctly).
dew wrote:

   ...

> When i implement this on a DSP processor, are there any specific > problems i will encounter.(of course, assuming that it has been coded > correctly).
You may want to use registers normally set aside for DSP-specific functions, and they must be saved and later restored if they have been set up for a task to be continued. Most DSP memory is segmented. Working RAM, the password buffer, and the stored database may all be in different segments. You will probably have to manage that explicitly. My dog is calling -- no kidding! I'll write again if I think of anything. Otherwise, C is C. Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;