> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by dew●March 17, 20072007-03-17
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).
Reply by dew●March 17, 20072007-03-17
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.
Reply by Jerry Avins●March 16, 20072007-03-16
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by Jerry Avins●March 16, 20072007-03-16
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by dew●March 16, 20072007-03-16
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=
>
> > 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.
Reply by Jerry Avins●March 15, 20072007-03-15
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.
>> ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
>
> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by dew●March 15, 20072007-03-15
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..
Reply by Jerry Avins●March 15, 20072007-03-15
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by dew●March 15, 20072007-03-15
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.