In Chapter 12 - negation we have seen that in German there are two different ways of negation, the one with nicht and the one with kein. This system doesn't change with the change in the tenses.

Examples negation with nicht     Er arbeitet jeden Tag. = He works every day.     Er arbeitet nicht jeden Tag. = He does not work every day.     Er arbeitete nicht jeden Tag. = He did not work every day.     Er hat nicht jeden Tag gearbeitet. = He has not worked every day.     Er hatte nicht jeden Tag gearbeitet. = He had not worked every day.     negation with kein     Ich sehe ein Haus. = I see a house.   Ich sehe kein Haus. = I don't see a house.   Ich sah kein Haus. = I did not see a house.     Ich habe kein Haus gesehen. = I haven't seen a house.     Ich hatte kein Haus gesehen. = I had not seen a house

As you see, the position of the negation changes depending on the tense. Is there a compound tense (present perfect or past perfect) then the negated object is moved after the modal verb and before the perfect participle.

This principle is also used when using other modal verbs:

Examples   Er muss viel arbeiten. = He has to work a lot.     Er muss nicht viel arbeiten. = He does not have to work a lot.

The question now is how is the word order with two objects in the sentence, the direct object as well as the indirect object. As said before the word order for compound tenses is

(subject) conjugated verb + indirect object + direct object + perfect participle (if the none or only one object is substituted with a personal pronoun)
(subject) conjugated verb + direct object + indirect object + perfect participle (if both objects are substituted with personal pronouns)

Examples   Sie hatte ihm das Auto geschenkt. = She had given the car to him.     Er hat es ihr gesagt. = He has told her.

The word order for negated phrases is the same as above, only the nicht is put before the perfect participle.

Examples Ich habe es ihm nicht gesagt. = I have not told him.     Sie hatte ihm das Auto nicht geschenkt. = She had not given him the car.

If we now make thing even a bit more complicated and use an attribut (a more detailed description) as above the word order is as follows:
(subject) conjugated verb + indirect object + direct object + (nicht) + attribute + perfect participle (if none or only one object is substituted by personal pronouns)
(subject) conjugated verb + direct object + indirect object + (nicht) + attribute + perfect participle (if both the objects are substituted by personal pronouns)

Examples Ich habe es ihm (nicht) gleich gesagt. = I have (not) told him right away.     Sie hatte ihm das Auto (nicht) erneut geschenkt. = She had (not) given him the car anew.