SRBs and missiles use grain to regulate thrust over time, as only exposed surface of the propellant burns.
But what causes propellant to burn only on the surface, and regulates the speed at which the surface burns? Surely not atmospheric oxygen supply (which is what causes similar property of free-burning solids) as it has oxidizer distributed throughout the volume; there's no apparently clear reason why the solid fuel couldn't just burn all at once throughout the volume; something puts it apart from common explosives which are effectively just that, a kind of fuel and oxidizer mix that burns all at once all throughout the volume, in enclosed space, releasing all the combustion products at once.
So - what chemical additives or properties set solid propellants apart from explosives?
If we have a pressure shock front travelling very fast through the material it is an explosion. The reaction inside the explosive is started by the sudden pressure rise, not by a temperature rise. But when the solid rocket fuel burns, we have a nearly constant pressure inside the rocket and no travelling shock front. The thermal conductivity of the fuel is much slower, the reaction in a deeper level of the propellant only starts when the temperature is high enough there. The outer layers of the propellant stay cool and protect the walls of the rocket from high temperatures. If the solid rocket is reuseable, the walls should not be damaged in the last seconds of the burn when the reaction zone comes close to the walls.
I've asked the same question on Chemistry.SE and got some more factors than mentioned in the answers here.
flexible binding agent (rubber), that prevents forming cracks under pressure, is essential to maintaining stable, low deflagration rate vastly lower than in blasting charges of the same composition.
modifying ratio of oxidizers (perchlorate, ammonium nitrate) regulates the speed; perchlorate burns faster.
catalysts like carbon and metals can increase the deflagration rate.
MIL-STD-286C. defines a method of determining linear burning rate of propellants.
So, essentially, first - applying a rubber-like binder is the critical part that reduces deflagration rate to "propellant speeds". Then, through "trial and error" the rate can be fine-tuned - adapted to requirements of construction, geometry and purpose of specific SRB/missile - through modifying oxidizer composition and catalysts. The final part is the grain shape inside the rocket, which regulates how area of deflagration changes over time, regulating thrust of the rocket over time - and the nozzle area, limiting the pressure (and deflagration rate) inside the SRB.
A propellant deflagrates, rather than explodes. The difference between them is that deflagration relies on the thermal energy of the flame front, rather than the energy of the shockwave caused by detonation.
The key to this process is a balance between two factors, the activation energy of the propellant and the temperature at which the propellant burns. This balance is set against the thermal diffusion of the propellant. If the heat cannot diffuse fast enough into the propellant, it won't stay lit. If it diffuses too fast... well... you wondered what keeps them from going boom?
Surface area, pure and simple. The more surface area visible, the faster the burning will occur.
As to what separates them from explosives, it is that the propellant is so tightly bound that only the surface can burn. If there are cracks, then solid rockets can in fact explode, so they are very carefully manufactured.
Looking through the description of APCP, I noticed that it contains metal powder. That means your assumption about the oxidizer isn't correct. At microscopic level, the oxidizer is not distributed throughout the volume of the metal. The distance between oxidizer molecules and metal atoms is measured in micrometers, not nanometers. Of course, a micrometer still isn't that much, which explains why the reaction is very quick once the propellant is vaporized. The atoms only need to travel those few micrometers before they can react. But that's not instant, and it limits the burn rate.